Учитывая 200 строк, что является хорошим способом ввода LUT значений отношений

Question

У меня 200 строк. Каждая строка имеет отношение (измеряется с плавающей запятой между 0 и 1) с каждой другой строкой. Эти отношения двусторонние; то есть отношения A / B == отношения B / A. Это дает n (n-1) / 2 отношений, или 19 800.

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

Я использую c ++, поэтому, вероятно, я бы использовал std :: map для хранения LUT. Вопрос в том, какой ключ лучше всего использовать для этой цели.

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

Мой подход заключается в создании уникального идентификатора для каждой пары слов. Например, учитывая слова «яблоко» и «апельсин», я объединяю их вместе как «апельсин» (в алфавитном порядке, сначала наименьший) и использую это в качестве значения ключа.

Это хорошее решение или кто-то может предложить что-то более умное? :)

Answer 1

Если boost / tr1 приемлем, я бы выбрал unordered_map с парой строк в качестве ключа. Тогда главный вопрос будет: что с порядком строк? Это может быть обработано хеш-функцией, которая начинается с лексической первой строки.

Примечание: это просто предложение после прочтения проблемы дизайна, а не исследования.

Answer 2

Как быстро "быстро"?Учитывая, что вам не важен порядок двух слов, вы можете попробовать карту следующим образом:

std::map<std::set<std::string>, double> lut;

Здесь ключ представляет собой set из двух слов, поэтому, если вы вставите «яблоко»"и" оранжевый ", то порядок такой же, как у" оранжевого "" яблока ", а учитывая, что set поддерживает оператор меньше чем, он может функционировать как ключ на карте.ПРИМЕЧАНИЕ: я намеренно не использовал pair для ключа, учитывая, что порядок там имеет значение ...

Я бы начал с чего-то довольно простого, такого как профиль, и посмотрел бы, насколько быстро / медленно поиск и т.д.перед тем, как посмотреть, нужно ли что-нибудь сделать умнее ...

Answer 3

В основном вы описываете функцию двух параметров с добавленным свойством, что порядок параметров не имеет значения.

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

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

Answer 4

Если ваши 200 строк находятся в массиве, ваши 20 100 значений сходства также могут быть в одномерном массиве.Все зависит от того, как вы индексируете этот массив.Скажем, x и y - это индексы строк, для которых вы хотите подобия.Поменяйте местами x и y, если необходимо, чтобы y> = x, затем посмотрите на запись i = x + y (y + 1) / 2 в большом массиве.

(x, y) of (0,0)), (0,1), (1,1), (0,2), (1,2), (2,2), (0,3), (1,3) ... приведет вас кзапись 0,1,2,3,4,5,6,7 ...

Таким образом, это оптимально использует пространство и дает более быстрый поиск, чем карта.Я предполагаю, что эффективность, по крайней мере, слегка важна для вас, поскольку вы используете C ++!

[если вас не интересуют значения самоподобия, где y = x, тогда используйте i = x + y (y-1) / 2 вместо].

Answer 5

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