Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Начинающим";
Текущий архив: 2010.10.31;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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

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


 
brother ©   (2010-08-10 11:05) [20]

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


 
Ega23 ©   (2010-08-10 11:06) [21]


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


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


 
Юрий Зотов ©   (2010-08-10 11:09) [22]


> admax_   (10.08.10 11:00) [17]

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


 
Sha ©   (2010-08-10 11:12) [23]

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

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


 
Sha ©   (2010-08-10 11:14) [24]

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


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


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

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


 
Sha ©   (2010-08-10 11:19) [26]

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

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


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

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



Страницы: 1 вся ветка

Форум: "Начинающим";
Текущий архив: 2010.10.31;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.51 MB
Время: 0.004 c
2-1280950446
mylasthit
2010-08-04 23:34
2010.10.31
как работать с модулем re_bmp?


2-1281369967
DROWSY
2010-08-09 20:06
2010.10.31
TIBCustomDataSet .RecordCount


15-1279359785
Knight
2010-07-17 13:43
2010.10.31
Как организовать внутренее взаимодействие в сетевом приложении?


2-1281339806
6ruse
2010-08-09 11:43
2010.10.31
Дата на первое число месяца


2-1281011430
Scot Storch
2010-08-05 16:30
2010.10.31
парсинг имени файла





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский