ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый поиск?
23 сообщений из 23, страница 1 из 1
Быстрый поиск?
    #33800709
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Предположительно есть два текстовых массива данных, необходимо прверить для каждого элемента из второго массива, имеется ли он в первом?
Есть две идеи:
1. Простой перебор на соответствие для каждого элемента(т.е. для массивов 1000 и 1000 элементов получим миллион сравнений)
2. Слить первый массив в одну строку, потом просто делать поиск строки второго массива в этой строке(записи достаточно структурированы, так что совпадений на стыке записей быть не должно). В этом случае получим 1000 поисков в одной длинной строке(вроде должны быть алгоритмы быстрого поиска, позволяющие получить выигрыш в производительности?)

Может кто подскажет что лучше? Или третий вариант?
...
Рейтинг: 0 / 0
19.06.2006, 17:38
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33800739
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
А где вариант "Использовать СУБД и не морочить голову"?)
...
Рейтинг: 0 / 0
19.06.2006, 17:50
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33800819
mike160
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mike160
Участник
Следует ничего не выдумывать, и пользоваться стандартными функциями поиска для данного языка. Это самое оптимальное.
Еще есть "Регулярные выражения".
...
Рейтинг: 0 / 0
19.06.2006, 18:18
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33800956
locky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locky
Участник
Первый файл - в сортированный массив, строку из второго - искать в
массиве дихотомией.
Применительно к дельфину - TStringList.Sorted=true, TStringList.IndexOf.


--
-------------------------
There's no silver bullet!
Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
19.06.2006, 18:55
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33800988
профф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
профф
Гость
Если оба массива отсортированы, то самы быстрый поиск будет типа такого:
Код:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
int i=0;
int j=0;
while(i<1000&&j<1000)
{
a=arr1 -arr2[j];
if(a==0){
...
}
else if(a<0)
{
i++;
}
else if(a>0)
{
j++;
}
}

...
Рейтинг: 0 / 0
19.06.2006, 19:03
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33801963
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
DocAlА где вариант "Использовать СУБД и не морочить голову"?)

Тут СУБД и использовалась-мне нужно сделать импорт/экспорт. У меня есть подозрение что поиск на полное совпадение по ~120 полям и переоткрытие запроса на каждую новую запись будет недетски тормозить.

Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
...
Рейтинг: 0 / 0
20.06.2006, 11:27
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33802039
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
zloy den
Правильный алгоритм уже был назван, но сформулирую его более четко.

1. Отсортировать оба массива.
2. Пройти параллельно по обоим массивам, сравнивая текущие элементы и продвигая тот из маркеров, который "меньше".
...
Рейтинг: 0 / 0
20.06.2006, 11:47
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33802288
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maXmo
Участник
zloy denПредположительно есть два текстовых массива данных, необходимо прверить для каждого элемента из второго массива, имеется ли он в первом?имхо, обычный count + inner join.
...
Рейтинг: 0 / 0
20.06.2006, 12:51
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33802436
профф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
профф
Гость
zloy den DocAlА где вариант "Использовать СУБД и не морочить голову"?)

Тут СУБД и использовалась-мне нужно сделать импорт/экспорт. У меня есть подозрение что поиск на полное совпадение по ~120 полям и переоткрытие запроса на каждую новую запись будет недетски тормозить.

Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
Просто к сведению: у него сложность в худшем случае n 2 , а в лучшем n (если я правильно понял), у меня в любом случае n.
...
Рейтинг: 0 / 0
20.06.2006, 13:32
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33804665
locky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locky
Участник
профф wrote:
> Тут СУБД и использовалась-мне нужно сделать импорт/экспорт. У меня есть
> подозрение что поиск на полное совпадение по ~120 полям и переоткрытие
> запроса на каждую новую запись будет недетски тормозить.
>
> Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
>
>
> Просто к сведению: у него сложность в худшем случае n^2 , а в лучшем n
> (если я правильно понял), у меня в любом случае n.
Это да, поиск слиянием будет быстрее, за исключением одного но: если
размерность массивов - достаточно велика, то может быть невыгодно
держать оба массива в памяти и сортировать их. Однако, если массивы
действительно размерностью 1000 - то поиск слиянием решается за один проход.


--
-------------------------
There's no silver bullet!
Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
21.06.2006, 11:02
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33806923
nikname
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikname
Гость
set<string> и set_intersection. Это - быстро. Ну и 1000 элементов - не до фига.
Возможно эффективнее первое множество засунуть в vector<string> , отсортировать Log n и потом искать эл-ты из второго множества upper_bound - n* log2 n
...
Рейтинг: 0 / 0
21.06.2006, 19:59
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33807067
LordMAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LordMAD
Участник
Вы, чего, народ!!! Читайте классику, Сэджвика, например. ..............................................................
...
Рейтинг: 0 / 0
21.06.2006, 21:21
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33807130
nikname
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikname
Гость
И что вы там вычитали? Неужто он порекомендовал заново изобретать двоичный поиск и писать классы? Ну и запретил использовать stl?
Если да, то забудьте то, что вы прочли, а если нет, то присоветуйте - что умное по теме вы вычитали.
...
Рейтинг: 0 / 0
21.06.2006, 22:06
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33807285
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
ЛордМэд

Вам замечание.
большая просьба отказаться от комментирования действий других участников форума. А приводить свою версию решения проблемы.
...
Рейтинг: 0 / 0
22.06.2006, 00:29
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33808445
профф
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
профф
Гость
locky
Это да, поиск слиянием будет быстрее, за исключением одного но: если
размерность массивов - достаточно велика, то может быть невыгодно
держать оба массива в памяти и сортировать их.
ИМХО даже если размерность высока на столько что не помещается в памяти, то тогда все равно сортировка слиянием, потом поиск слиянием. Сначала отсортировать любым удобным способом куски, которые помещаются в памяти, и записать в файлы, потом применить поиск слиянием (до конца сортировать даже и не надо). Полюбому должно быть быстрее поиска в неотсортированных данных такого же объема :)
...
Рейтинг: 0 / 0
22.06.2006, 13:07
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33809090
LordMAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LordMAD
Участник
tchingizЛордМэд

Вам замечание.
большая просьба отказаться от комментирования действий других участников форума. А приводить свою версию решения проблемы.
Замечание, возможно, справедливое. Только прошу не каверкать мой ник.

Итак:
1. Использовать хэши.
...
Рейтинг: 0 / 0
22.06.2006, 15:31
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33809690
nikname
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikname
Гость
LordMAD[quot tchingiz]ЛордМэд
1. Использовать хэши.
Хэши есть в stl, т.е. не требуется реализовывать алгоритм руками => Сэджвик не проханже, в данном случае.
КРоме того выбор хорошей хэш-функции - задача не тривиальная. Выигрыш не очевиден, а объём накладных расходов по сравнению с сортированным массивом строк выше.

Собственно то, что я предложил уже предложено было выше, я просмотрел. И мне кажется, что это - оптимальный с точки зрения:
а) Времени реализации (при условии, что язык поддерживает коллекции)
б) требований к оперативной памяти - только необходимое
в) быстродействия - n* log2(n)
...
Рейтинг: 0 / 0
22.06.2006, 17:47
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33809734
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
zloy den DocAlА где вариант "Использовать СУБД и не морочить голову"?)

Тут СУБД и использовалась-мне нужно сделать импорт/экспорт. У меня есть подозрение что поиск на полное совпадение по ~120 полям и переоткрытие запроса на каждую новую запись будет недетски тормозить.

Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
А я бы сделал LEFT JOIN... Для СУБД объём данных просто смешной.
...
Рейтинг: 0 / 0
22.06.2006, 17:57
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33809765
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
Примерно так:
SELECT второй_массив.значение FROM второй_массив LEFT JOIN первый_массив ON второй_массив.значение = первый_массив.значение WHERE первый_массив.значение IS NULL
Это выдаст значения из второго массива, которые отсутствуют в первом.
...
Рейтинг: 0 / 0
22.06.2006, 18:02
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33809926
locky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locky
Участник
DocAl wrote:
> Примерно так:
> SELECT второй_массив.значение FROM второй_массив LEFT JOIN первый_массив
> ON второй_массив.значение = первый_массив.значение WHERE
> первый_массив.значение IS NULL
> Это выдаст значения из второго массива, которые отсутствуют в первом.
.... предварительно заставив человека установить какой-нито сервер,
залить в него данные....
угу...

--
-------------------------
There's no silver bullet!
Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
22.06.2006, 19:13
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33810044
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
locky
DocAl wrote:
> Примерно так:
> SELECT второй_массив.значение FROM второй_массив LEFT JOIN первый_массив
> ON второй_массив.значение = первый_массив.значение WHERE
> первый_массив.значение IS NULL
> Это выдаст значения из второго массива, которые отсутствуют в первом.
.... предварительно заставив человека установить какой-нито сервер,
залить в него данные....
угу...

--
-------------------------
There's no silver bullet!
Posted via ActualForum NNTP Server 1.3
zloy den
Тут СУБД и использовалась-мне нужно сделать импорт/экспорт. У меня есть подозрение что поиск на полное совпадение по ~120 полям и переоткрытие запроса на каждую новую запись будет недетски тормозить.
Ась? Какой такой сервер установить?
...
Рейтинг: 0 / 0
22.06.2006, 20:33
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33810356
LordMAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LordMAD
Участник
niknameХэши есть в stl, т.е. не требуется реализовывать алгоритм руками => Сэджвик не проханже, в данном случае.
А кто говорил о ручной реализации хэшей?
niknameКРоме того выбор хорошей хэш-функции - задача не тривиальная.
Это по-твоему повод не использовать хэши?
niknameВыигрыш не очевиден, а объём накладных расходов по сравнению с сортированным массивом строк выше.
Вот чтобы таких глупостей не писать, почитай хотя бы книжки!
niknameСобственно то, что я предложил уже предложено было выше, я просмотрел. И мне кажется, что это - оптимальный с точки зрения:
а) Времени реализации (при условии, что язык поддерживает коллекции)
б) требований к оперативной памяти - только необходимое
в) быстродействия - n* log2(n)
"Когда кажется - креститься надо" (с)
...
Рейтинг: 0 / 0
23.06.2006, 08:15
| Ответить | Цитировать | Написать  
Быстрый поиск?
    #33810865
locky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locky
Участник
DocAl wrote:

> Ась? Какой такой сервер установить?
сорри, был невнимателен.

--
-------------------------
There's no silver bullet!
Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
23.06.2006, 11:40
| Ответить | Цитировать | Написать  
23 сообщений из 23, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый поиск?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]