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

[Ship_1]

Здравствуйте!
История. (можно опустить, вопросы выделены дальше)
Что-то решил заморочиться простыми числами и решил сделать программу для их поиска. Сначала программка казалась простой. Поиск идёт банальным делением чисел цикла от 2 до N на список уже найденных простых чисел, в который они добавляются, если число не удалось поделить нацело. Пока верхний предел был не больше 1 000 000. А вот когда решил замахнуться на 1 000 000 000 - тут уже стал серьёзно задумываться
Во-первых, цикл завешивает всю программу, и на больших числах уже может оказаться проблемным определить: работает программа и проверяет очередное число по всем предыдущим найденным или просто зависла. (Вывод каждого цикла сразу отрубил для экономии времени на вывод, ограничив его каждым 10 000)
Во-вторых, если у меня за всё возможное время работы программы (с утра и до вечера) все числа найтись не успеют - как быть с этим, если вывод всех найденных простых чисел у меня происходит только после завершения поиска (возможно, тоже экономит время)?
Я раньше никогда не работал с потоками. Решил, что пришло таки время. Забил в поисковик, вроде, нашёл. Поверхность оказалась не сложной и интересной. Запустил цикл в поток, заодно в потоке объявил четыре переменных, по которым была бы возможность дополнительно отслеживать процесс и остановить его при необходимости без потери найденных данных.
ОК. За день все циклы действительно не прошли. Сохранил имеющиеся данные, решил чуть подправить программку для возможности продолжения поиска. Одно изменение было элементарным - задать произвольное начало цикла по Edit. Второе - загрузка уже найденного списка. И вот тут начались ещё одни проблемы.
Найденные простые числа я добавляю в TStringList (попытался работать с просто TList, но почему-то у меня не захотело работать деление i mod prochis[j] (prochis: TList). Решил перейти на TStringList.
За прошлый день у меня обработалось больше 17 000 000 чисел, из которых больше 1 000 000 оказалось простыми. В конце работы список простых чисел у меня через цикл выводится в Memo, из которого я его без проблем, выделив всё, скопировал и сохранил в блокноте.
А вот при загрузке так просто уже не получилось.

prochis.LoadFromFile()

завешивал программу.
Создал отдельную загрузку в ListBox через чтение текстового файла Readln. Зависает, но по появляющемуся "ползунку" ListBox'а хоть понятно, что приняла данные и надо просто подождать.
Дальше пытался перенести уже оттуда в ProChis. Сначала через

ProChis.Assign(ListBox1.Items);

. Опять зависал. Тогда опять циклом пошёл. Вроде, сработало. Запустил поиск дальше.
Но как быть теперь?

Вопросы:
Как ещё переделать программку чтоб она не зависала без возможности проверить работу в момент загрузки найденной базы перед новым стартом?
Как обезопасить себя от зависания при выводе найденной базы в Memo после остановки?
Как обезопасить себя от переполнения TStringList?

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

Текущий код программки:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TOneMoreThread=class(tthread)
  private
  public
    Prover_Chis, On_Prov_Chis, Last_Prich: integer; // проверяемое число и (On_Prov_Chis) простое число число, на которое идёт деление
    IsWork: boolean;
  protected
    procedure execute; override;
  end;
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    Edit1: TEdit;
    Label1: TLabel;
    Button2: TButton;
    Label2: TLabel;
    Button3: TButton;
    Edit2: TEdit;
    Button4: TButton;
    ListBox1: TListBox;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  ProChis:TStringList;
  OneMoreThread:TOneMoreThread;
  
implementation

{$R *.dfm}


procedure TOneMoreThread.execute;
var i, j:integer;
//    k:integer;
    t1,t2:TDateTime;
    IsPro:Boolean;
begin
  inherited;
  ProChis:=TStringList.Create;
  IsWork:=true;
  For i:=0 to Form1.ListBox1.Items.Count-1 do
  begin
    ProChis.Add(Form1.ListBox1.Items.Strings[i]);
    Prover_Chis:=i;
    On_Prov_Chis:=i-Form1.ListBox1.Items.Count;
    Last_Prich:=Form1.ListBox1.Items.Count;
  end;
  i := StrToInt(Form1.Edit2.Text);
  If i=StrToInt(ProChis[ProChis.Count-1]) then i:=i+1;
  ShowMessage('Последнее простое число: '+ProChis[ProChis.Count-1]+#13+'Первое число нового старта: '+IntToStr(i));
//  k := 1;
  t1 := now;
  Form1.Memo1.Lines.Insert(0,TimeToStr(t1));
  while (i <= StrToInt(Form1.Edit1.Text)) and IsWork do
  begin
    Prover_Chis := i;
    ispro := true;
    for j := 0 to ProChis.Count-1 do
    begin
      On_Prov_Chis := j;
      if i mod StrToInt(prochis[j]) = 0 then
      begin
        IsPro := false;
        break;
      end;
    end;
    if ispro then
    begin
      prochis.Add(IntToStr(i));
      Last_Prich := i;
//      k := k + 1;
    end;
    if i mod 10000 = 0 then
    begin
      Form1.Memo1.Lines.Insert(0,'Цикл '+IntToStr(i div 10000)+'*10 000');
      t2 := now;
      Form1.Memo1.Lines.Insert(1,TimeToStr(t2));
    end;
    i := i + 1;
  end;
  t2 := now;
  Form1.Memo1.Lines.Insert(0,'Финальное время: '+TimeToStr(t2));
//  print(prochis)
  Form1.Memo1.Lines.Insert(0,'Затрачено времени: '+TimeToStr(t2-t1));
  Form1.Memo1.Lines.Insert(0,'Последнее проверенное число: '+IntToStr(i));
  Form1.Memo1.Lines.Insert(0,prochis.Text);
  ProChis.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  OneMoreThread:=TOneMoreThread.Create(false); // << false означает авто запуск потока
  OneMoreThread.FreeOnTerminate:=true; // << Уничтожение после выполнения
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  Label2.Caption:='Проверяемое число: '+IntToStr(OneMoreThread.Prover_Chis)+#13+
                  'Проверяется числом: '+IntToStr(OneMoreThread.On_Prov_Chis)+#13+
                  'Последнее найденное простое число: '+IntToStr(OneMoreThread.Last_Prich);
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
  OneMoreThread.IsWork:=false;
end;

procedure TForm1.Button4Click(Sender: TObject);
var
  t:TextFile ;
  x:String ;
begin
  AssignFile(t,ExtractFilePath(Application.ExeName)+'База простых чисел.txt');
  Reset(t);
  while not eof(t) do
  begin
    Readln(t,x);
    ListBox1.Items.Add(x) ;
  end;
  CloseFile(t);
  showmessage(inttostr(ListBox1.Items.Count)) ;
end;

end.

У меня пока только одна мысль: разбить TStringList на несколько, по 100 тыс. строк, например. Создать безразмерный массив из таких строк. Но как начнёт себя вести программа, когда таких списков окажется 200? 200 списков по 100 тыс. записей. А при достижении циклом 1 млрд их уже будет около 600.

[evg_m]

Запустил цикл в поток, заодно в потоке объявил четыре переменных, по которым была бы возможность дополнительно отслеживать процесс и остановить его при необходимости без потери найденных данных.

прекрасно.
Для остановки потока УЖЕ есть готовый функционал.
свойство terminated (имеющая ровно тот же смысл и задачу что и твоя переменная IsWork ). Да и используемая ровно также (в проверках и условиях цикла обработки).

while ...  and IsWork  and not terminated

плюс к этому для ЕЁ установки в true есть специальная процедура Terminate.

  OneMoreThread.IsWork:=false;
  OneMoreThread.Terminate;

конечно ничто не мешает ПРОДОЛЖАТЬ использовать свой механизм управления работой (IsWork).

есть правило ВЫЗЫВАЕМЫЙ (в данном случае поток OneMoreThread) должен как можно меньше знать о том кто его использует (в данном случае Form1).
его могут в теории вызвать САМЫЕ разные формы, а то и вовсе какая нибудь консольная программа БЕЗ формы. В твоем случае это пока не так, НО ....

в идеале в теле потока Не должно быть ни одного упоминания о Form1.

В то же время ВЫЗЫВАЮЩИЙ (form1) может (и имеет право) многое знать о том кого он вызвал (он же и так знает кого именно он вызвал).
Form1 имеет право НЕЗАВИСИМО от работы потока периодически (обычно это бывает таймер) узнать его состояние (те самые четыре переменные ) и отобразить их так как считает нужным и так часто как считает нужным (просто меняем интервал срабатывания таймера).

ЕСЛИ поток все же решает САМ работать с формами (VCL объектами), то для этого ЕМУ требуется использовать Synchronize (на форуме это самая распространенная тема в потоках). В некоторых простых случаях "прокатывает" и без, НО ...

ЭТО общие замечания.

Как ещё переделать программку чтоб она не зависала без возможности проверить работу в момент загрузки найденной базы перед новым стартом?

вопрос не понял.

Как обезопасить себя от зависания при выводе найденной базы в Memo после остановки?

а может и не надо выводить в мемо все! вывести к примеру только последний.
а для хранения использовать все тот же TStringList
и сохранять его ВНЕ потока сразу же после нахождения очередного простого числа.
еще одна переменная задаваемая в потоке, я нашел новое простое число, прошу вас сохраните наши числа.
вот здесь-то и пригодится Synchnize как защита от записи очередного числа ДО выполнения записи данных в файл.
и сброс этой переменной после записи данных.

Как обезопасить себя от переполнения TStringList?

место для строк ~3Гб (максимально адресуемая память на 32-разрядной платформе)
количество строк 2^31 = 2 147 483 647 Мало ???

для оптимизации добавления СРАЗУ большого числа строк читаем про CapaCity.
визуальные компоненты + BeginUpdate/EndUpdate.

[Ship_1]

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

количество строк 2^31 = 2 147 483 647 Мало ???

Вроде, должно хватить... По грубым подсчётам из уже имеющихся данных в итоге у меня получится около 60 000 000 строк.

Поясню первый вопрос: как лучше загрузить большой объём данных из текстового файла в TStringList, чтобы можно было следить за процессом загрузки для понимания, что программа пока не зависла? Напрямую через цикл While i, открыв текстовый файл через AssignFile, считывая информацию через Readln добавлять считанную строку в StringList? Для отслеживания периодически выводить эту i. Нормально ли будет переместить этот цикл загрузки из Button4Click сразу в поток, или для грамотного программирования этого делать не стоит?

По поводу работы с формами из потока: просто я хотел бы, чтобы кроме текущего значения в любой момент, цикл выводил бы значения через определённое количество (каждые 10 000 циклов). Думаю, для этого Вы и упомянули Synchronize. Попробую разобраться с этим, как появится ещё промежуток времени для этого.

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

а для хранения использовать все тот же TStringList
и сохранять его ВНЕ потока сразу же после нахождения очередного простого числа.

Т.е. завести второй TStringList вне потока и дублировать им тот, который в потоке? И сохранять его в файл после каждого числа? Или чего? Не до конца понял. На всякий случай: между нахождениями каждого нового простого числа проходит весьма мало времени. 10-ти тысячных циклов у меня проходит примерно по два с половиной в минуту (другими словами, ~25 000 циклов в минуту). На каждые 20 чисел, судя по имеющимся данным, есть как минимум одно простое число. Т.е., если я всё правильно посчитал, у меня находится условно по 20 простых чисел в секунду.
UPD: после 20-го миллиона скорость замедлилась до 20 000 циклов в минуту.

[Аватар]

Это не самый эффективный алгоритм. Посмотри решето Эратосфена и его модификации

На каждые 20 чисел, судя по имеющимся данным, есть как минимум одно простое число.

Не-а. Чем дальше в лес, тем плотность распределения уменьшается

[Ship_1]

Аватар, спасибо за совет, обязательно попробую найти и понять, но эта программка стала мне уже интересна ещё и с точки зрения работы с большими списками. После изучения вопроса по Вашей наводке, возможно, сделаю другую программку.

[evg_m]

Т.е. завести второй TStringList вне потока и дублировать им тот, который в потоке?

можно (и скорее даже нужно) использовать один и тот же. А для согласованности работы потока и сохранения использовать synchnize.

И сохранять его в файл после каждого числа? Или чего?

можно и так, но скорее так: В момент "проверки" состояния потока по таймеру определяем:
- наличие желания сохранить (например прошло 5 минут после предыдущего сохранения) и
- наличие "новой" информации в данных (переменная потока отвечающая за это).
- .... другие пожелания (условия)
при выполнении условиЙ Делаем сохранение, "сбрасываем" наличие новых данных(изменяем переменную), отмечаем время нашего нового сохранения и выполняем другие действия (по "другим пожеланиям").

просто я хотел бы, чтобы кроме текущего значения в любой момент, цикл выводил бы значения через определённое количество (каждые 10 000 циклов).

как избавиться от Form1 в потоках, но оставить возможность АКТИВНОГО общения, чтобы поток мог сам "сообщать" форме (точнее кому-бы то ни было) о своем состоянии.
http://www.programmersforum.ru/showp...87&postcount=5 и далее по ссылкам.

[Ship_1]

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

можно (и скорее даже нужно) использовать один и тот же.

Т.е. сделать вот так?

procedure TForm1.Button1Click(Sender: TObject);
begin
  ProChis:=TStringList.Create;
  OneMoreThread:=TOneMoreThread.Create(false); // << false означает авто запуск потока
  OneMoreThread.FreeOnTerminate:=true; // << Уничтожение после выполнения
  Form1.Memo1.Lines.Insert(0,prochis.Text);
  ProChis.Free;
end;

(убрав соответствующие строки из потока) Это что-то поменяет? Или я так и не понял мысль?

[evg_m]

begin
  ProChis:=TStringList.Create;  // если объект предназначен для работы в потоке то и создавать наверное лучше там, но это не обязательно.
  OneMoreThread:=TOneMoreThread.Create(false); // << false означает авто запуск потока
  OneMoreThread.FreeOnTerminate:=true; // << Уничтожение после выполнения
  Form1.Memo1.Lines.Insert(0,prochis.Text);
  ProChis.Free;  //  а вот это здесь ни-ни!!! список мы удалили, НО поток продолжает работать (а точнее только-только начинаем работу) 
// и с чем ему прикажете работать.
end;

Если мы оставляем создание здесь( в Form1), то у потока есть OnTerminate.

OneMoreThread:=TOneMoreThread.Create;
OneMoreThread.OnTerminate:=MyThreadIsFinish; // когда будешь завершать свою работу, то  будем делать это

Tform1 =class

private
  procedure MyThreadisFinish(sender: TObject);
end;

procedure Tform1.MyThreadisFinish(Sender: TObject);
begin
  Prochis.SaveToFile; //если надо и мы не делаем это где-то еще и другими спсобами
  Prochis.Free; //вот теперь когда МЫ знаем что поток закончил работу мы можем это сделать!
end;

[Ship_1]

evg_m, спасибо! Теперь есть о чём пока поразмышлять на досуге в эхтом направлении. Я вот только пока не понял: если я цикл начальной загрузки хочу тоже в поток отправить, мне для него надо отдельный class(tthread) делать и отдельную execute?
Аватар, глянул на это решето. Может, оно и быстрее будет, но у этого цикла один недостаток: мы не получим простых чисел пока алгоритм не выполнится полностью.
А здесь же все числа, оставшиеся после прохождения цикла, уже простые, и если надоест или нет времени больше ждать - у нас уже есть какая-то база простых чисел.
Но всё равно ещё раз спасибо, я попробую реализовать и этот алгоритм.

[Аватар]

1. Он не просто быстрее, а на много быстрее. Для того, что хочешь получить он возможно выполнится за вполне приемлемое время
2. Кто мешает прерывать вычисления и сохранять промежуточные результаты, восстанавливая их при следующем входе? В твоем подходе можно, почему здесь нельзя?
3. Ну и да, речь конечно не идет о числах порядка 2^64 и выше

По поводу времени вычислений посмотри и сравни со своим. Там конечно алгоритм решета вылизан до предела, но все же