Работа с большим списком: как обезопаситься от переизбытка?

[kropotkina-alice]

Сообщение от Ship_1

За прошлый день у меня обработалось больше 17 000 000 чисел, из которых больше 1 000 000 оказалось простыми

За целый день??? Обалдеть... Вы на арифмометре "Феликс" их вычисляете?
У меня старенький ноутбук и вот результаты (правда я своим способом это делала, причем вывод шел непрерывно, а я в это время спокойно пользовалась интернетом и играла в "Косынку"):

[Ship_1]

Аватар Ниффигасе скорость... 0.12 сек. до 1 000 000 000...
Но это же хитрым путём сделанная продвинутая программка Жаль, числа не выводит.
Если я реализую решето в изначальном виде, модифицированном только началом с квадрата, мне всё равно до такого будет как черепахе до ракеты ) Но уже стало ещё интереснее всё-таки хоть как-то реализовать этот метод. Путём, доступным моему текущему пониманию.

[Ship_1]

kropotkina-alice Ключевая фраза:

Сообщение от kropotkina-alice

(правда я своим способом это делала):

Каким способом делал я - вы видите. Не думаю, чтобы этим же (моим) способом Вы достигли бы своих скоростей. Если не жалко, поделитесь своим.

[kropotkina-alice]

Конечно не жалко...
Ни потоков, ни каких-либо малодоступных для понимания хитрых приемов - все решается "в лоб":

  tb,te: TTime;

implementation

{$R *.dfm}

function prostoe_chislo (n : Int64) : boolean;
var  r: Int64;
begin
if n<2 then
 result:=false
else
 begin
  r:=2;
  result:=true;
  while (r*r<=n)and result do
  if n mod r=0 then
   result:=false else
    inc(r);
 end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
Memo1.ScrollBars:=ssVertical;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i: longint;
begin
Memo1.Clear;
tb:=Time;
for i:=2 to StrToInt(Edit2.Text) do
 if prostoe_chislo(i) then
  Memo1.Lines.Add(IntToStr(i));
te:=Time;
ShowMessage('На вычисление'+IntToStr(Memo1.Lines.Count)+' простых чисел из '+Edit2.Text+' затрачено '+IntToStr(Round(100000*(te-tb)))+' секунд');
end;

[Ship_1]

kropotkina-alice Спасибо! Поанализирую по дороге домой что тут происходит и почему я до такого не додумался
Хотя после 50 000 у меня окно зависло пока не доделало всё до конца.
UPD:
Подумал. Получается, что вы каждое число просто делите на каждое число, меньшее его половины? Не удивительно, что я не догадался до этого способа. Вроде, у меня практически то же, но я делю только на простые числа. Не думал, что обращение к списку настолько тормозит процесс, что простой перебор всех чисел подряд будет намного быстрее...
Кстати, добавляя к TStringList найденные числа, а не выводя их сразу в Memo у меня результат поиска до 17 000 000 составил 67 секунд.
Спасибо Вам!
Вот дела-то...

[Serge_Bliznykov]

а попробуйте ещё такой алгоритм:

function isPrime(X: LongInt): boolean;
var i, lim: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     lim := trunc(sqrt(x));
     while i <= lim do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;

просто для сравнения.

p.s. ну а решето должно быть ещё намного быстрее

[Ship_1]

Serge_Bliznykov Спасибо, тоже попробую.
По методу kropotkina-alice за пару часов проходит около 500 млн.

Но я таки реализовал решето Эратосфена!
Разбил процесс на этапы:
1. формирование булевской матрицы
2. само вычисление
До 17 млн второй этап занял пол секунды!
Т.к. вывод простых чисел до 17 млн уже подтормаживал - решил и его выделить в отдельный этап:
3. вывод результата.

Ввёл в Edit миллиард.
Формирование матрицы заняло пол секунды.
Поиск простых чисел занял 12.3 секунды!!
А вот на выводе в Memo выкинулась проблема с памятью...
Тогда решил выводить прямо в текстовый файл (AssignFile -> Rewrite -> Writeln -> CloseFile). На всякий случай подцепил ProgressBar (меняя его раз в 10 тыс.циклов).
Вывод в файл занял практически 34 секунды

Теперь вот не знаю чем этот файл открыть. ) Блокнот зависает. Ворд вообще сказал, что не работает с файлами, большими 512 МБ. А мой файлик получился 527 МБ.

Вопрос на засыпку: а как, всё-таки, вывести их теперь в программке для просмотра?

[Аватар]

А чего в нем интересного, чтобы пялиться на него? А вообще можно не целиком его в память, а кусками читать. Все равно сразу все не увидеть. А если смотреть на них, то интересно смотреть как-то графически, что бы визуально подмечать закономерности распределения. Например разворачивая их по спирали или еще как. Глядишь и закономерность распределения найдешь. Это покруче теоремы Ферма будет

[evg_m]

хотите поднять скорость НЕ меняя алгоритма программы? конечно это не будет так кардинально, как при смене алгоритма, но все же...

избавляемся от постоянных StrToint.

1.

  while (i <= StrToInt(Form1.Edit1.Text)) and IsWork do

TOneMoreThread=class(tthread)
  public
    FmaxProvChis: integer; //будем хранить в потоке верхнюю границу нашего поиска
....

  while (i <= FmaxProvChis) and IsWork do

ну и кнопочка на форме где будет задание этой границы (можно конечно обойтись и БЕЗ кнопки, но пусть будет кнопка)

 OneMoreThread.FmaxProvChis:=strtoint(Edit1.Text);

и не забывать задать(или изменить) эту границу при запуске потока.

P.S. заодно исключили одно использование Form1 в потоке.

2.

     if i mod StrToInt(prochis[j]) = 0 then

TStringList имеет свойство для хранения "личных" данных каждой строки Objects[].
правда оно имеет не совсем тот тип данных, но да это не беда.

     if i mod integer(prochis.Objects[j]) = 0 then

и конечно же если мы этим хотим пользоваться, то его надо и заполнять.

      prochis.Add(IntToStr(i));
      prochis.AddObject(Inttostr(i), TObject(i));

заполнять надо не только при нахождении нового числа, но и при старте программы (чтении из файла).
и в этом случае без цикла чтения уже никак не обойдешься.
LoadFromFile не будет этого делать(заполнять свойство Objects[]).
хотя можно сначала сделать LoadFromFile а потом пройтись в цикле и cделать

prochis.LoadFromfile(...);
for j:=0 to prochis.count-1 do 
   prochis.Objects[j]:=TObject(strtoint(prochis.Strings[j]));

[Ship_1]

Вот только не пойму как теперь шагнуть за пределы integer.
С int64 не хочет работать for и скорость создания первичной матрицы уменьшилась в 4 раза при переходе на while.