ускорение цикла

← →
admax_ (2010-08-10 10:17) [0]

Добрый день, уважаемые форумчане!
Помогите, пожалуйста, в следующем вопросе.
Есть два файла структуры типа:
123|qwe|qwe|sdsf|dsfsf|1234...
Они содержат очень много строк.
Необходимо построчно сравнить эти строки в каждом из файлов.
Тоесть, берем элементы (те что между ||) первой строки первого файла и сравниваем ее с элементыми каждой строки второго файла. Далее берем элементы 2 строки первого файла и сравниваем ее с элементами каждой строки второго файла...
While not EOF(f1) do begin ReadLn(f1,st1); ... While not EOF(f2) do begin ReadLn(f2,st2); ... end; end;
В результате получается очень большой цикл, на выполнение которого затрачивается очень много времени.
Подскажите, пожалуйста, алгоритм по которому можно организовать данный цикл быстрее.

← →
Ega23 © (2010-08-10 10:19) [1]

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

Загрузить в списки, отсортировать, а потом сравнивать.

← →
admax_ (2010-08-10 10:24) [2]

> Загрузить в списки, отсортировать, а потом сравнивать.

В какие списки? И как это повлияет на производительность, если к-во строк останется неизменным.

← →
Sha © (2010-08-10 10:28) [3]

Если строки небольшие, их мало, или в них много повторений/совпадений
1. переписать данные в array of string или TStringList
2. сортировать
3. сравнить
Иначе можно попробовать использовать хеши вместо строк.

← →
Sha © (2010-08-10 10:30) [4]

> admax_ (10.08.10 10:24) [2]
> В какие списки?
> И как это повлияет на производительность, если к-во строк останется неизменным.

Количество сравнений посчитай сначала.

← →
12 © (2010-08-10 10:30) [5]

> > Загрузить в списки, отсортировать, а потом сравнивать.
>
>
> В какие списки? И как это повлияет на производительность,
> если к-во строк останется неизменным.

диск меньше тыркать будет, что уже лучше

а вообще, наверное так:
Сначала в обоих файлах сделать преобразование элементов в числа
например, /123/ - три байта код символа 1 join код символа 2 join код символа 3
(если возможно, конечно)
и сравнивать integer числа

← →
admax_ (2010-08-10 10:40) [6]

> Иначе можно попробовать использовать хеши вместо строк.

Хеши это конечно хорошо, но речи идеть о Делфи ;) Или я где-то пропустил, что и здесь уже можно использовать полноценные хеши.

← →
Юрий Зотов © (2010-08-10 10:44) [7]

LOL

← →
admax_ (2010-08-10 10:45) [8]

> Если строки небольшие, их мало, или в них много повторений/совпадений1.
> переписать данные в array of string или TStringList2. сортировать3.
> сравнить

Опишу задачу более подробно.
Файл1:
2121|abc|c|2|hfg|fgh|7
2311|jhft|gfh|3|ddhfgcn|fghfgh|32
6543|hse|h|45|sfg|fghfg|2
8905|fgr|rte|342|fdg|fghf|43
...

Файл2:
2111|авп|c|2|hfg|fgh|7
2311|jhft|gfh|3|ddhfgcn|fghfgh|32
6543|hse|h|45|sfg|fghfg|2
6535|fgr|rte|342|fdg|fghf|43
...
Берем элементы "abc" "hfg" "2121" первой строки первого файла и ищем строку во втором файле, содержащую такие же элементы в соответствующих местах.

← →
Ega23 © (2010-08-10 10:46) [9]

> Или я где-то пропустил, что и здесь уже можно использовать
> полноценные хеши.

Н-да...

← →
Sha © (2010-08-10 10:47) [10]

> Юрий Зотов © (10.08.10 10:44) [7]

Скоро поколение пепси забудет, что батоны раньше ели.

← →
admax_ (2010-08-10 10:50) [11]

> диск меньше тыркать будет, что уже лучше

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

← →
admax_ (2010-08-10 10:51) [12]

> > Или я где-то пропустил, что и здесь уже можно использовать
> > полноценные хеши.Н-да...

Поподробней, пожалуйста...

← →
Ega23 © (2010-08-10 10:53) [13]

> Поподробней, пожалуйста...

Что "поподробней"? Берёшь, считаешь хэш от твоих строк. Например crc32. И их уже после сравниваешь, что будет гораздо быстрее.

← →
Sha © (2010-08-10 10:55) [14]

> admax_ (10.08.10 10:45) [8]
> Файл1:
> 2121|abc|c|2|hfg|fgh|7
> Берем элементы "abc" "hfg" "2121" первой строки первого файла...

Судьба остальных?

Как это вяжется с

> Необходимо построчно сравнить эти строки в каждом из файлов.

← →
admax_ (2010-08-10 10:56) [15]

> Судьба остальных?Как это вяжется с > Необходимо построчно
> сравнить эти строки в каждом из файлов.

Извиняюсь, что изначально не так выразился. Я ведь дописал: "оесть, берем элементы (те что между ||) первой строки первого файла и сравниваем ее с элементыми каждой строки второго файла."

← →
Sha © (2010-08-10 10:59) [16]

> берем элементы

Это значит берем некоторые элементы
или берем все элементы?

← →
admax_ (2010-08-10 11:00) [17]

> > Поподробней, пожалуйста...Что "поподробней"? Берёшь, считаешь
> хэш от твоих строк. Например crc32. И их уже после сравниваешь,
> что будет гораздо быстрее.

Наверное под хэшем мы понимаем разные вещи. Для меня это некий массив, имеющий ключь и значение. Обьясните, пожалуйста, что здесь имеется ввиду.

← →
admax_ (2010-08-10 11:02) [18]

> Это значит берем некоторые элементыили берем все элементы?

Именно некоторые.

← →
Sha © (2010-08-10 11:05) [19]

> Наверное под хэшем мы понимаем разные вещи.
> Для меня это некий массив, имеющий ключь и значение.

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

ТЗ я так и не понял...

> Наверное под хэшем мы понимаем разные вещи. Для меня это
> некий массив, имеющий ключь и значение. Обьясните, пожалуйста,
> что здесь имеется ввиду.

http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F

> admax_ (10.08.10 11:00) [17]

Hash и hash table - вещи несколько разные. Но в обоих случаях Delphi (как и любой другой язык) тут ни при чем. И если человек этого не понимает, то, значит, ему пока еще не следует высказывать свои оценки языков. Иначе получается известная басня Крылова.

> admax_ (10.08.10 11:02) [18]
> Именно некоторые.

Тогда Strings загоняешь значения между раздетелем,
а в Objects - номер строки, далее см. [1] или [3]

раздетель - это разделитель

← →
admax_ (2010-08-10 11:17) [25]

> Тогда Strings загоняешь значения между раздетелем,а в Objects
> - номер строки, далее см. [1] или [3]

Поподробней, пожалуйста...

> Поподробней, пожалуйста.

Можно, см. справку к TStringList.

← →
admax_ (2010-08-10 11:26) [27]

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

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