Поиск в текстовом массиве. Быстрый алгоритм. , Идеи, решения, алгортимы

Задача такая. Дан двумерный массив m(13,n), в общем случае типа variant (в терминах VB). Одна из колонок - текстовые значения. Среди этих текстовых значений надо найти произвести проверку на наличие элемента, и если элемента нет, о добавит еще одну строку. А если есть то в другой массив занести значение индекса строки.

Как быстрее осуществить данную операцию? Ключевое слово - побыстрее. Надо как-то оценить быстроту алгоритма.

Впервые сталкиваюсь с такой задачей, в голову пришла следующая идея.
Искомый столбец представить в виде текстовой строки, где уже и искать включение. Для того, чтобы определить индекс элемента в массиве, после каждого элемента ставить какой-нибудь знак, например перенос строки, а после него число - соответствующее индексу строки в массиве m(13,n). Что-то типа
Вася(13)1(13)Петя(13)2Вова(13)3
Соответственно, найдя элемент, мы вытаскиваем его индекс.

Понятно, что такие задачи уже наверняка, решали... Если кто тыкнет - буду премного благодарен.

Сообщение отредактировано: Vlasssov - 16.10.10, 19:02

Цитата Vlasssov @ 04.10.10, 15:59

в голову пришла следующая идея

Подготовительные операции к реализации твоей идеи гарантированно сожрут любой выигрыш от её гениальности.
Если записи не сортированы по этому полю - нет ничего быстрее прямого просмотра. А если сортированы - то бинарный поиск.

Добавлено 04.10.10, 17:40
Другое дело, если по этому массиву нужно обработать по описанному алгоритму большой массив строк - тогда разумнее отсортировать массив (вернее, проиндексировать его) по этому полю.

И сразу вопрос: а как вы собираетесь сортировать текстовые строки? По алфавиту? Каждое текстовое поле содержит текстовый фрагмент, который можно отсортировать по алфавиту. То есть имеем даже при включении элемента в текстовый массив проверку идентичности все строке.

Теперь о подготовительном этапе. Почему он сожрет-то? Массив формируется по мере нахождения элементов в него не включенных. То есть добавляем элемент в массив и параллельно добавляем в строку.

Добавлено 05.10.10, 05:15

Цитата Akina @ 04.10.10, 17:39

Если записи не сортированы по этому полю - нет ничего быстрее прямого просмотра. А если сортированы - то бинарный поиск.

Да.. а есть где-нибудь реализация бинарного поиска?
А, ну да...
http://codingrus.ru/readarticle.php?article_id=2152

А нет.. А как придумать уникальный числовой ключ по текстовым строкам? А то не получается бинарный поиск...

Сообщение отредактировано: Vlasssov - 05.10.10, 05:52

Цитата Vlasssov @ 05.10.10, 05:14

как придумать уникальный числовой ключ по текстовым строкам

Это называется хэширование. Только надо понимать, что при свёртке всегда существует вероятность коллизии.

Цитата Vlasssov @ 05.10.10, 05:14

И сразу вопрос: а как вы собираетесь сортировать текстовые строки? По алфавиту?

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

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

Цитата Akina @ 05.10.10, 06:25

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

Интересно ак как осуществлять бинарный поиск на неотсортированном массиве? А тут при отсуствии рагмета текса в строке, просто добавляем элемент к массиву. Дешево и сердито.

Теперь вопрос. Где будет быстрее осуществляться поиск в текстовой переменной, или в отсортированном массиве? В случае поиска в строке не надо сортировать массив...
Речь все равно идет о ключе, только в данном случае ключ будет представлять из себя текстовую строку.

Бинарное дерево поиска, например, RB или AVL-Tree, позволит быстро искать и вставлять элементы.
Хэш-таблица для коротких данных обычно побыстрее работает, но для строк нужно хэш вычислять для всего объема данных, тогда как сравнения строк при поиске в дереве будут в основном задействовать небольшое число символов (собственно, это зависит от особенностей набора данных).

Цитата Vlasssov @ 05.10.10, 10:34

Интересно ак как осуществлять бинарный поиск на неотсортированном массиве?

Этого я не знаю...

Добавлено 05.10.10, 19:32

Цитата MBo @ 05.10.10, 10:59

Бинарное дерево поиска, например, RB или AVL-Tree, позволит быстро искать и вставлять элементы.

Построение дерева собсно ничем не лучше сортировки.

Если бы все внимательно прочитали задачу, то там написано, что при отсутствии в массиве уникального ключа ДОБАВЛЯЕТСЯ еще один элемент. Так что тут мы будем делать вот такой ключ, в виде массива
k(3,n)
где
k(0,n) - бинарное значение текстовой строки
k(1,n) - значение индекса в основном массиве
k(2,n) - ссылка на индекс предыдущего элемента в массиве ключа
k(3,n) - ссылка на следующий элемент

Осуществлять будем бинарный поиск, а на последнем шаге, в случае остуствия элемента добавлять новый элемент в конец массива, при этом прописывая в элементах

k(2,n) - ссылка на индекс предыдущего элемента в массиве ключа
k(3,n) - ссылка на следующий элемент

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

Akina
>Построение дерева собсно ничем не лучше сортировки.
Один раз - не лучше. Здесь, насколько я понял - динамика - и на каждом шаге добавление элемента в дерево занимает logN времени, и структура остается упорядоченной, а вот сортировка на каждом шаге - не фонтан...

Если же все-таки у автора оффлайн-режим (весь набор данных доступен сразу), то, конечно, сортировка.

Цитата Vlasssov @ 06.10.10, 02:05

Если бы все внимательно прочитали задачу, то там написано, что при отсутствии в массиве уникального ключа ДОБАВЛЯЕТСЯ еще один элемент

Судя по ответам, все прочитали внимательно и не пропустили информацию о добавлении.

Цитата Vlasssov @ 06.10.10, 02:05

мы будем делать вот такой ключ, в виде массива

А вот о создании постоянного индекса (вернее, о построении связного списка) мы слышим впервые. Как и о том, что на даноом массиве будет обрабатываться большой объём входных данных.

Цитата Vlasssov @ 06.10.10, 02:05

в случае остуствия элемента добавлять новый элемент в конец массива

Почему в конец? почему не в середину в соответствии с порядком сортировки по k(0,n)?
Но MBo совершенно прав - для твоей задачи в том виде, в котором она озвучена на текущий момент, оптимальным решением будет бинарное дерево.

Цитата Akina @ 06.10.10, 04:41

Цитата Vlasssov @ 06.10.10, 02:05

Если бы все внимательно прочитали задачу, то там написано, что при отсутствии в массиве уникального ключа ДОБАВЛЯЕТСЯ еще один элемент

Судя по ответам, все прочитали внимательно и не пропустили информацию о добавлении.

Цитата Vlasssov @ 06.10.10, 02:05

мы будем делать вот такой ключ, в виде массива

А вот о создании постоянного индекса (вернее, о построении связного списка) мы слышим впервые. Как и о том, что на даноом массиве будет обрабатываться большой объём входных данных.

Цитата Vlasssov @ 06.10.10, 02:05

в случае остуствия элемента добавлять новый элемент в конец массива

Почему в конец? почему не в середину в соответствии с порядком сортировки по k(0,n)?
Но MBo совершенно прав - для твоей задачи в том виде, в котором она озвучена на текущий момент, оптимальным решением будет бинарное дерево.

Что быстрее обработать - текстовую переменную, или массив данных?

Добавлено 06.10.10, 11:39

Цитата Akina @ 06.10.10, 04:41

удя по ответам, все прочитали внимательно и не пропустили информацию о добавлении.

Включение элемента в массив повлечет за собой сдвиг n-го количества элементов.

Если порядок следования строк не играет роли, то советую добавлять их в лексикграфическом порядке (т.е. aaa<aab<baa<bba<bbb<bbc<caa) соответсвенно поиск производить бинарным поиском за n*log(n) и если элемент найдется, то ничего делать и не придется, а если нет, то мы будем знать место куда добавить новый элемент. Можно конечно реализовать кэширование, но я не уверен что это будет быстрее моего варианта(хотя реализация должна быть проще)

>Что быстрее обработать - текстовую переменную, или массив данных?
Что значит - обработать?

Цитата Vlasssov @ 06.10.10, 11:37

Включение элемента в массив повлечет за собой сдвиг n-го количества элементов.

В СОРТИРОВАННЫЙ массив с СОХРАНЕНИЕМ сортировки - да. Иначе - с какой бы стати? пихай в конец, и всё.

Решал подобную задачу. Нужно было искать совпадение в большом массиве строк. Каждая строка (элемент массива) длинной около 10 символов. Размерность массива около 3000 элементов, но поиск был очень объемный, т.к. шаблонных строк для поиска было тоже около 3000. Т.е. если искать линейно, то получалось около 9000000 сравнений, что занимало относительно много времени.

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

Т.е. есть массив от 0 до n. Бинарным поиском находим i-тый элемент в массиве. Если он не равен строке которую мы ищем, то вставляем ее на i-1 или i+1, в зависимости от array[i] > str или array[i] < str.