Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый поиск? / 23 сообщений из 23, страница 1 из 1
19.06.2006, 17:38
    #33800709
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
Предположительно есть два текстовых массива данных, необходимо прверить для каждого элемента из второго массива, имеется ли он в первом?
Есть две идеи:
1. Простой перебор на соответствие для каждого элемента(т.е. для массивов 1000 и 1000 элементов получим миллион сравнений)
2. Слить первый массив в одну строку, потом просто делать поиск строки второго массива в этой строке(записи достаточно структурированы, так что совпадений на стыке записей быть не должно). В этом случае получим 1000 поисков в одной длинной строке(вроде должны быть алгоритмы быстрого поиска, позволяющие получить выигрыш в производительности?)

Может кто подскажет что лучше? Или третий вариант?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.06.2006, 17:50
    #33800739
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
А где вариант "Использовать СУБД и не морочить голову"?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.06.2006, 18:18
    #33800819
mike160
mike160
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
Следует ничего не выдумывать, и пользоваться стандартными функциями поиска для данного языка. Это самое оптимальное.
Еще есть "Регулярные выражения".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.06.2006, 18:55
    #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, 19:03
    #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
| Ответить | Цитировать | Написать  
20.06.2006, 11:27
    #33801963
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
DocAlА где вариант "Использовать СУБД и не морочить голову"?)

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

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

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

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

Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
Просто к сведению: у него сложность в худшем случае n 2 , а в лучшем n (если я правильно понял), у меня в любом случае n.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.06.2006, 11:02
    #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, 19:59
    #33806923
nikname
nikname
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
set<string> и set_intersection. Это - быстро. Ну и 1000 элементов - не до фига.
Возможно эффективнее первое множество засунуть в vector<string> , отсортировать Log n и потом искать эл-ты из второго множества upper_bound - n* log2 n
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.06.2006, 21:21
    #33807067
LordMAD
LordMAD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
Вы, чего, народ!!! Читайте классику, Сэджвика, например. ..............................................................
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.06.2006, 22:06
    #33807130
nikname
nikname
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
И что вы там вычитали? Неужто он порекомендовал заново изобретать двоичный поиск и писать классы? Ну и запретил использовать stl?
Если да, то забудьте то, что вы прочли, а если нет, то присоветуйте - что умное по теме вы вычитали.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.06.2006, 00:29
    #33807285
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
ЛордМэд

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

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

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

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

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

Спасибо locky за вариант для Дельфи-его я наверное и буду использовать
А я бы сделал LEFT JOIN... Для СУБД объём данных просто смешной.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.06.2006, 18:02
    #33809765
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
Примерно так:
SELECT второй_массив.значение FROM второй_массив LEFT JOIN первый_массив ON второй_массив.значение = первый_массив.значение WHERE первый_массив.значение IS NULL
Это выдаст значения из второго массива, которые отсутствуют в первом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.06.2006, 19:13
    #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, 20:33
    #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
| Ответить | Цитировать | Написать  
23.06.2006, 08:15
    #33810356
LordMAD
LordMAD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
niknameХэши есть в stl, т.е. не требуется реализовывать алгоритм руками => Сэджвик не проханже, в данном случае.
А кто говорил о ручной реализации хэшей?
niknameКРоме того выбор хорошей хэш-функции - задача не тривиальная.
Это по-твоему повод не использовать хэши?
niknameВыигрыш не очевиден, а объём накладных расходов по сравнению с сортированным массивом строк выше.
Вот чтобы таких глупостей не писать, почитай хотя бы книжки!
niknameСобственно то, что я предложил уже предложено было выше, я просмотрел. И мне кажется, что это - оптимальный с точки зрения:
а) Времени реализации (при условии, что язык поддерживает коллекции)
б) требований к оперативной памяти - только необходимое
в) быстродействия - n* log2(n)
"Когда кажется - креститься надо" (с)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.06.2006, 11:40
    #33810865
locky
locky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый поиск?
DocAl wrote:

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

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


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