усовершенствование цикла

← →
inex (2007-10-12 14:22) [0]

Подскажите пожалуйста, можно ли как-то усовершенствовать следующий цикл:

var a, b : array[0.500000] of string; i, y : integer; ... //заполняются элементы массивов ... for i:=0 to 500000 do for y:=0 to 500000 do if a[i]=b[y] then...

Когда я запускаю программу, она очень долго отрабатывает данный цикл.
Может можно как-то по другому организовать данный цикл?

← →
Dennis I. Komarov © (2007-10-12 14:28) [1]

А оно действительно надо, или это для атомной войны?

← →
Dennis I. Komarov © (2007-10-12 14:29) [2]

[1] касаемо
> array[0.500000] of string;

← →
Маша Шрайбер © (2007-10-12 14:33) [3]

>> Когда я запускаю программу, она очень долго отрабатывает данный цикл.

здесь вообще-то два цикла. и всего 500001*500001 итераций. причем никчемных.
вопрос - кому нужен этот ..?

← →
_max_ (2007-10-12 14:43) [4]

Ребята, ну подскажите тогда, пожалуйста, другой вариант.
Задача следующая. Есть тестовый файл с большим кол. строк.
В этом файле есть повторяющиеся записи. Нужно отфильтровать эти записи.
Делаю я следующим образом. Создал два массива элементы которых являлись строками файла. После чего я сравнивал кажый элемент первого массива с каждым элементом второго массива (приведенный вишецикл).
Согласен, что безобразно я это делаю, с точки зрения программирования, но задачу как-то нужно решить.

← →
Маша Шрайбер © (2007-10-12 14:46) [5]

TStringList + F1 и читать и думать, и читать и думать!

← →
Сергей М. © (2007-10-12 14:51) [6]

> задачу как-то нужно решить

Именно своими средствами ? Или воспользоваться готовыми не возбраняется ?

← →
_max_ (2007-10-12 14:54) [7]

> Именно своими средствами ? Или воспользоваться готовыми
> не возбраняется ?

Своими, т.к. это одна из многочисленных задач, которые мне нужно будет решить. И все они отличаются друг от друга, но и в то же время все они будут работать с подобными циклами.

← →
_max_ (2007-10-12 14:57) [8]

> TStringList + F1 и читать и думать, и читать и думать!

TStringList? Какая разница, или содержимое файла я помещю в массив или в Strings? Что там что там я буду перелистывать все допустимые варианты данным циклом?

← →
Dennis I. Komarov © (2007-10-12 14:57) [9]

Мне всеже интересно, откуда взято "500000"?

← →
_max_ (2007-10-12 15:04) [10]

> Мне всеже интересно, откуда взято "500000"?

Ну не 500000, а 235000 - кол-во строк файла.
Это я так, к примеру написал.

← →
Маша Шрайбер © (2007-10-12 15:05) [11]

>> _max_ (12.10.07 14:54) [7]
>> _max_ (12.10.07 14:57) [8]

Как видно, это вам дали такое учебное задание. Тогда вопросы скорости вас не должны беспокоить. А только лишь алгоритмика.

← →
_max_ (2007-10-12 15:13) [12]

> Как видно, это вам дали такое учебное задание. Тогда вопросы
> скорости вас не должны беспокоить. А только лишь алгоритмика

Не совсем так! В принципе ничего страшного не было бы, если данная задача выполнялася ну скажем за минут 5. Но не 2, 3 и более часов, как в моем примере.

← →
Маша Шрайбер © (2007-10-12 15:20) [13]

>> _max_ (12.10.07 15:13) [12]

Для гордого показа своего успешного решения преподу достаточно на 10*10 строках.
Если не поставлена специальная задача оптимизации.

← →
Zeqfreed © (2007-10-12 15:20) [14]

Задача сводится к сортировке и последующему удалению повторяющихся идущих друг за другом строк.

← →
_max_ (2007-10-12 15:28) [15]

Задача стоит конкретно. Есть файл со строками:

Пупкин1 А.И. 3456378654
Пупкин2 А.П. 4538293647
Пупкин3 С.Р. 3456378654
...
И так 235000 строк.

Как видно число 3456378654 повторяется в 2 строках как минимум
(не исключено, что далее оно еще повстречается). Нужно с этого файла выбрать все записи с неповторяющимся числом (2 столбец).
Просто в голову ничего не приходит, как использование массивов.
Вот что-бы было что-то на подобе хешов!

← →
Маша Шрайбер © (2007-10-12 15:32) [16]

>> _max_ (12.10.07 15:28) [15]

Так это учебная задача? Или нет?

← →
Dennis I. Komarov © (2007-10-12 15:36) [17]

> [15] _max_ (12.10.07 15:28)

Базу тебе надо нормальную, с ключом и индексами. А не это файлы текстовые

← →
_max_ (2007-10-12 15:38) [18]

> Так это учебная задача? Или нет?

В своем роде учебная, ну как самообразование.
А вообще нет!

← →
_max_ (2007-10-12 15:41) [19]

> Базу тебе надо нормальную, с ключом и индексами. А не это
> файлы текстовые

Это то ясно, ну а все-таки, как можно ли как-то максимализировать процесс сортировки?

← →
Сергей М. © (2007-10-12 15:44) [20]

> максимализировать

Эт чиво такое ?)

Ты к постам Маши Шрайбер (С) проникся вообще-то ?)

← →
Dennis I. Komarov © (2007-10-12 15:45) [21]

> [18] _max_ (12.10.07 15:38)

- У вас гранаты учебные?
- В своем роде учебные, а вообще нет.
:)

> [19] _max_ (12.10.07 15:41)

Если хочешь извращаться:
1. Загрузить в TStringList
2. Отсортировать
3. Удалить повторы.

← →
palva © (2007-10-12 16:02) [22]

Надо сразу сказать, что StringList будет отсортированным и игнорирующим повторы. Метод add будет возвращать индекс. Пример:
{$APPTYPE CONSOLE} uses Classes; var sl: TStringlist; begin sl := TStringlist.Create; sl.Sorted := True; sl.Duplicates := dupIgnore; WriteLn(sl.Add("14321234")); // 0 WriteLn(sl.Add("14321235")); // 1 WriteLn(sl.Add("14321236")); // 2 WriteLn(sl.Add("14321237")); // 3 WriteLn(sl.Add("14321236")); // 2 WriteLn(sl.Add("14321237")); // 3 sl.Free; end.
Вы видите, что если добавляемая строка в списке уже есть, то возвращается не индекс добавленной строки, а индекс существующей. Отсюда алгоритм:
Создается TStringList. Читается входной файл и переписывается в выходной. Из каждой строки извлекаем значение второго столбца и пытаемся добавить в список. Если возвращаемый индекс равен индексу последней добавленной строки плюс единица, то строка дубликатов (пока) не имеет - переписываем ее в выходной файл и обновляем последний добавленный индекс. В противном случае строку игнорируем.

← →
palva © (2007-10-12 16:04) [23]

> Надо сразу сказать
Надо сразу установить такие свойства StringList

← →
_max_ (2007-10-12 16:06) [24]

Понял, буду думать другие решения.
Всем спасибо за внимание!

Зы, думаю inex на меня не обиделся :)

← →
_max_ (2007-10-12 16:08) [25]

Большое спасибо, palva, за пример.
Буду пробовать!

← →
palva © (2007-10-12 16:10) [26]

> TStringList? Какая разница, или содержимое файла я помещю в массив или в Strings?
Разница та, что ты вряд ли будешь осуществлять дихотомический поиск дубликата. А StringList будет. Правда StringList на самом деле никакой не список, а вектор, поэтому вставки в середину будут довольно затратными. Для большей эффективности можно использовать не StringList, а организовать двоичное дерево. Но это надо программировать самому.

← →
Anatoly Podgoretsky © (2007-10-12 16:12) [27]

Огласите задачу, а не ваше представление как ее решать.
Главное какая цель.

← →
Anatoly Podgoretsky © (2007-10-12 16:14) [28]

И на всякий случай, в приведеном примере нет повторяющихся строк

Пупкин1 А.И. 3456378654 Пупкин2 А.П. 4538293647 Пупкин3 С.Р. 3456378654

← →
palva © (2007-10-12 16:15) [29]

> поэтому вставки в середину будут довольно затратными
Пардон, вставок в середину не будет, поскольку дубликаты игнорируются.

← →
palva © (2007-10-12 16:17) [30]

> вставок в середину не будет

Фигню написал. Вставки будут, поскольку список отсортирован.

← →
_max_ (2007-10-12 16:17) [31]

> И на всякий случай, в приведеном примере нет повторяющихся
> строк

Имелись ввиду части строк, как видно с данного примера.
Извините, если завел в заблуждение.

← →
_max_ (2007-10-12 16:20) [32]

> Anatoly Podgoretsky © (12.10.07 16:12) [27]
> Огласите задачу, а не ваше представление как ее решать.Главное
> какая цель.

> _max_ (12.10.07 15:28) [15]

> _max_ (12.10.2007 16:17:31) [31]

А мне не понятно, почему должен удаляться Пупкин1, а не Пупкин3 и на каком основании, какая в этом цель.

← →
_max_ (2007-10-15 10:06) [35]

> А мне не понятно, почему должен удаляться Пупкин1, а не
> Пупкин3 и на каком основании, какая в этом цель.

Должен удалится и 1 и 3 Пупкин а остаться только строка:

Пупкин2 А.П. 4538293647

Но это, если файл состоит из 3 строк, а если из более чем 200000, это уже затрудняет процесс.
Тоесть, должны удалится все записи с повтряющимися номерами, а остаться только с уникальным номером.

> Должен удалится и 1 и 3 Пупкин а остаться только строка:
Тогда извините, я вас неправильно понял. Мой алгоритм palva © (12.10.07 16:02) [22] не подойдет

А если будет только

Пупкин1 А.И. 3456378654 Пупкин3 С.Р. 3456378654

Тогда что?
В любом случае желательно применить какую ни будь базу, которая поддерживает SQL и работает в памяти (InMemoryDataset)

← →
zorik (2007-10-15 15:58) [38]

1. Создать список записей
TMyItem = record
Name: String;
Code: String; (или Integer)
end;
2. Загрузить в список из файла
3. Отсортировать по Code
4. Пробежать по списку и удалять. Удалять так. Запомнить первое значение. Организовать цикл для проверки пока следующее равно сохраненному. Удалить от первого до того что нашли.
Пример удаления. Не проверял, набросал на скорую руку
var DeleteFirst: Boolean; //признак повторяючихся записей i := 0; while i <= List.Count - 2 do //на 1 меньше чем длина begin TempCode := List[i].Code; //запомнили значение j := i + 1; //индекс следуещего значения DeleteFirst := False; //не удалять первое while TempCode = List[j] do begin if not DeleteFirst then DeleteFirst := True; //удалить первое //удаляем повторяющееся. j не увеличиваем, поскольку список ссунется List.Delete(j); end; //если были повторяющиеся -- удалить i-тое, иначе увеличить i if DeleteFirst then List.Delete(i) else i := i + 1; end;

Ох уж эти сказочки, ох уж эти сказочники (с)

← →
zorik (2007-10-15 16:10) [40]

← →
koha (2007-10-15 22:33) [41]

- интересно, а такой алгоритм сколько работать будет?

var Form1: TForm1; LFull,LShort,LSource: TStrings; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); var i,N,T: integer; begin //........... //загружаем LSource //...... //представим, что уже загрузили LSource каким-нибудь способом N:=14; for i := 0 to LSource.Count - 1 do begin T:=LShort.IndexOf(LSource.Strings[i][n]); if T = -1 then begin LFull.Add(LSource.Strings[i]); LShort.Add(LSource.Strings[i][n]); end else begin LFull.Delete(i); LShort.Delete(i); end; end; //.................. end;

← →
koha (2007-10-15 22:58) [42]

- Сорри кучу ошибок исправил, ну вобщем работающий пример, но далек от совершенства.

var Form1: TForm1; LFull,LShort,LSource: TStrings; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); var i,N,T: integer; St: String; begin st:=" "; // 10 цифр LFull := TStringList.Create; LShort := TStringList.Create; LSource := TStringList.Create; try LSource.LoadFromFile("c:\Archive\test.txt"); //........... //загружаем LSource //...... //представим, что уже загрузили LSource каким-нибудь способом N:=14; for i := 0 to LSource.Count - 1 do begin Move(LSource.Strings[i][N],ST[1],10); memo1.Lines.Add(st); T:=LShort.IndexOf(St); if T = -1 then begin LFull.Add(LSource.Strings[i]); LShort.Add(ST); end else begin LFull.Delete(i-1); LShort.Delete(i-1); end; end; //.................. memo1.Text:=LFull.Text; finally LFull.Free; LShort.Free; LSource.Free; end; end;

← →
koha (2007-10-15 23:29) [43]

- создал этих Пупкиных 1460160 одинаковых сторок и в разных местах 4 строки изменил
время ушло на загрузку и сортировку всего ~ 1.5 секунды (грубый подсчет), Процессор: Core 2 Duo T5600 (1,83 Mг).

необходимо исправить строки:
LFull.Delete(i-1);
LShort.Delete(i-1);
на:
LFull.Delete(T);
LShort.Delete(T);

усовершенствование цикла Найти похожие ветки