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

Задача такая. Дан двумерный массив 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.

ищется по условии задачи ПОЛНОЕ соответствие строки или может быть ее часть?
т е если дана строка: "Привет МИР! Солнце светит, погода прекрасна"
то может ли быть поиск фразы "Солнце светит" или "да" или вся фраза целиком с точностью до символа?

Цитата MBo @ 06.10.10, 11:57

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

Во многих языках программирования поиск фрагмента в сроке реализован в виде функций. Вот в VisualBasic
instr
http://msdn.microsoft.com/ru-ru/library/8460tsh1%28VS.90%29.aspx
То есть, если добавлять в строковую переменную очередной найденный фрагмент, и потом осуществлять с помощью стандартной функции поиска из любого языка (ну мы не берем случай ассемблера), то не будет ли быстрее, просто осуществить поиск с помощью данной функции?

С бинарным деревом поиска, проблема такая... Если искать построить бинарное дерево по уже упорядоченному массиву, то бинарный поиск выродится в прямой перебор, потому что двиение будет по одной ветке.

Цитата Akina @ 06.10.10, 12:12

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

Akina, вы говорите загадками. То вы хихикаете, про бинарный поиск в НЕОТСОРТИРОВАННОМ массиве,

Цитата Akina @ 05.10.10, 19:29

Цитата (Vlasssov @ 5.10.10, 13:34)
Интересно ак как осуществлять бинарный поиск на неотсортированном массиве?

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

тот начинаете хихикать, про

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

Подготовительные операции к реализации твоей идеи гарантированно сожрут любой выигрыш от её гениальности.

При этом пишите:

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

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

Еще раз вам расскажу про задачу. Может что я не так написал. Есть неупорядоченный никаким образом массив текстовых срок. Например:
$avArray[0] = "JPM"
$avArray[1] = "Holger"
$avArray[2] = "Tylo"
$avArray[3] = "Larry"
$avArray[4] = "Jeremy"
$avArray[5] = "Tylo"
$avArray[6] = "Cyberslug"
$avArray[7] = "Nutster"
$avArray[8] = "Holger"
$avArray[9] = "Tylo"

Сформированный абсолютно "от балды. " При этом в нем есть , как можно заметить, повторяющиеся элементы. Так вот надо составить массив

$avArray[0] = "JPM"
$avArray[1] = "Holger"
$avArray[2] = "Tylo"
$avArray[3] = "Larry"
$avArray[4] = "Jeremy"
$avArray[5] = "Cyberslug"
$avArray[6] = "Nutster"

С уникальными именами. Очень похоже на SQL-запрос о повторяющихся записях. Полученный на выходе массив не должен быть упорядочен. Так понятней? Причем с каждым поиском массив будет увеличиваться. Естественно, что главной трудоемкой задачей будет проверка на уникальность.

Добавлено 07.10.10, 05:12

Цитата FasterHarder @ 06.10.10, 13:24

ищется по условии задачи ПОЛНОЕ соответствие строки или может быть ее часть?
т е если дана строка: "Привет МИР! Солнце светит, погода прекрасна"
то может ли быть поиск фразы "Солнце светит" или "да" или вся фраза целиком с точностью до символа?

Вся фраза целиком с точностью до символа. Потому что по сути это набор из уникальных имен, в приведенном примере, это можно проиллюстрировать вот так:
Текстовая строка "JPM Holger Tylo Larry Jeremy Cyberslug Nutster"
Ну и соответственно поиск, например "JPM".

Цитата Vlasssov @ 07.10.10, 05:08

если добавлять в строковую переменную очередной найденный фрагмент, и потом осуществлять с помощью стандартной функции поиска из любого языка (ну мы не берем случай ассемблера), то не будет ли быстрее, просто осуществить поиск с помощью данной функции?

instr - функция небыстрая, кстати...

Цитата Vlasssov @ 07.10.10, 05:08

Akina, вы говорите загадками. То вы хихикаете, про бинарный поиск в НЕОТСОРТИРОВАННОМ массиве,

я?

Цитата Vlasssov @ 07.10.10, 05:08

Еще раз вам расскажу про задачу.
[skipped]
Полученный на выходе массив не должен быть упорядочен. Так понятней? Причем с каждым поиском массив будет увеличиваться. Естественно, что главной трудоемкой задачей будет проверка на уникальность.

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

Первая задача решается сортировкой без изменения порядка следования исходных данных с использованием результата в дополнительной структуре - т.е. фактически построением индекса по исходному массиву. Для максимального снижения накладных расходов при выполнении задачи 2 это скорее всего бинарное дерево.
Когда первая задача решена, вторая фактически тоже решена - проверяется присутствие нового элемента в массиве, при его отсутствии он добавляется в произвольное место, а в дерево добавляется соотв. лист, при необходимости ветка.

Наибольшую проблему представляет процесс физического удаления дублей элементов. И тут можно пойти двумя путями. Оба, впрочем, начинаются с одного и того же - построения битовой карты использования элементов (само собой, строится она в процессе выполнения первого этапа). Т.е. если элемент использован, на него есть ссылка в дереве-индексе - единичка, если элемент не использован, является дублем, а ссылка в дереве идёт на другую его копию - нолик. А вот далее - либо производится сжатие массива непосредственно по завершении составляления карты (при этом наиболее быстрым является перенос последнего использованного элемента на место первого неиспользующегося, повторяем до закрытия всех "дырок"), либо добавление новых элементов на втором этапе выполняется в первый неиспользуемый элемент (при отсутствии неиспользуемых элементов в середине массива получается уже добавление в конец).

Следует отметить, что появление этой проблемы - удаления неиспользуемых элементов,- есть следствие использования для хранения данных массива. Если бы (а может, ещё не поздно?) была использована коллекция элементов - этой проблемы бы просто не возникало... кстати, коллекции бывают и сортированные - т.е. сортировка будет выполняться непосредственно в момент добавления скрытыми методами коллекции, а бинарный поиск можно будет применять по коллекции без дополнительных действий и телодвижений.

Vlasssov
>то не будет ли быстрее, просто осуществить поиск с помощью данной функции?

В общем - поиск по дереву быстрее.


>Если искать построить бинарное дерево по уже упорядоченному массиву, то бинарный поиск выродится в прямой перебор, потому что двиение будет по одной ветке.

Во-первых, по упорядоченному массиву легко строится идеально сбалансированное дерево (средний элемент взять за корень, повторить для левой и правой половины и т.д.). Но реальный смысл это имеет только для статического набора данных.

Во-вторых, на практике в большинстве случаев используются сбалансированные (самобалансирующиеся) деревья - два вида я уже упоминал,

Цитата Akina @ 07.10.10, 05:29

Наибольшую проблему представляет процесс физического удаления дублей элементов.

А вот и нет, в случае дубля выполняется некоторая функция. Поэтому удаление дублей в данном случае не подойдет. Но это я не оговорил в условии, хотя речь шла о формировании массива.

Цитата MBo @ 07.10.10, 06:00

Во-первых, по упорядоченному массиву легко строится идеально сбалансированное дерево (средний элемент взять за корень, повторить для левой и правой половины и т.д.). Но реальный смысл это имеет только для статического набора данных.

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

Цитата MBo @ 07.10.10, 06:00

В общем - поиск по дереву быстрее.

Поверим на слово...

Цитата Akina @ 07.10.10, 05:29

Следует отметить, что появление этой проблемы - удаления неиспользуемых элементов,- есть следствие использования для хранения данных массива. Если бы (а может, ещё не поздно?) была использована коллекция элементов - этой проблемы бы просто не возникало... кстати, коллекции бывают и сортированные - т.е. сортировка будет выполняться непосредственно в момент добавления скрытыми методами коллекции, а бинарный поиск можно будет применять по коллекции без дополнительных действий и телодвижений.

Хм.. А создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом? Просто массив можно создать с избыточной размерностью. В моем случае (реальная задача) количество элементов в любом случае не будет превышать 30000.

Сообщение отредактировано: Vlasssov - 07.10.10, 07:07

Цитата Vlasssov @ 07.10.10, 07:06

создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом?

плюс память на создание и хранение ключа, если он не задаётся явно. Но у тебя им будет одно из полей массива - так что... впрочем, ты просто попробуй.

Цитата Vlasssov @ 07.10.10, 07:06

массив можно создать с избыточной размерностью

А коллекции это вообще по барабану.

Добавлено 07.10.10, 07:43

Цитата Vlasssov @ 07.10.10, 07:06

это я не оговорил в условии

Так... чего ещё мы не знаем?

Цитата Akina @ 07.10.10, 07:43

Так... чего ещё мы не знаем?

Ну вообще то речь изначально не об исключении дублей, а о поиске...

Ок, забиваем на дубли. При построении дерева и в дальнейшем при поиске по барабану, есть там дубли или нет.

Цитата Akina @ 07.10.10, 07:54

Ок, забиваем на дубли. При построении дерева и в дальнейшем при поиске по барабану, есть там дубли или нет.

Да ладно!!! По скорости обработки - есть.

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


То каждая в случае, частичной отсортированности, либо левая, либо правая ветка, будут упорядоченными массивами, где можно осуществлять бинарный поиск. То есть надо по идее, запоминать еще каким по счету в правой или левой ветке идет элемент. Тогда можно будет осуществлять поиск в бинарной массива, с последующим добавлением нового узла...
Грубо говоря, первый элемент бинарного дерева, разбивает множество чисел (в нашем случае это целые числа) на два подмножества, где является ка раз тем средним элементом, с которым идет сравнение в случае бинарного поиска. Поэтому надо переходит не к следующему элементу, а искать середину в правой и левой подветке. А уже потом добавлять элемент.

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

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

Цитата Vlasssov @ 16.10.10, 02:17

Тут еще одна идея в голову пришла..

<бла-бла-бла>

А можно еще нарисовать на стене оранжевый круг...

Афтар, почему ты не хочешь рассматривать предложенное решение с использованием хэш-таблицы, тем более что для данного случая она легко реализуется? Строками хэш-таблицы будут обычные текстовые строки переменной длины (динамическа строка), в которые пихаем ключи через разделитель. Поиск по строке делаем instr-ом.

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

Цитата Vlasssov @ 07.10.10, 07:06

А создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом?

От того, что сортировка запихнута в нутро коллекции, быстрее оно работать не станет. Тебе надо совсем от сортировок уйти.