Без машины ты не такой крутой. Самый быстрый список поиска

У меня есть коллекция структур. Каждая структура имеет 2 ключа. Если я запрашиваю, используя ключ №1, я должен получить ключ №2 взамен и наоборот.

Когда у вас есть мощь .NET Framework, писать код на рабочем столе легко. Я пишу код на .NET Micro Framework, которая представляет собой очень ограниченное подмножество инфраструктуры. Например, что касается коллекций, в моем распоряжении только массивы и объекты ArrayList.

Так, например, вот список структур:

Key #1        Key #2 
6             A
7             F
8             Z
9             B

Поэтому, когда я запрашиваю 8, я должен получить Z. Когда я запрашиваю Z, я должен получить 8.

Я ищу наиболее быстрый и наименее ресурсоемкий поиск с использованием массивов или ArrayList. Устройство, для которого я кодирую, - это процессор ARM младшего класса, поэтому мне нужно оптимизировать его как можно раньше.


c# .net-micro-framework
person AngryHacker    schedule 15.10.2009    source источник
comment
Какой объем данных? Для предоставленного образца самый быстрый подход является самым простым: сохранить данные в списке и повторить его ...   -  person Marc Gravell    schedule 15.10.2009
comment
Объем данных невелик. Вероятно, будет от 60 до 100 наименований.   -  person AngryHacker    schedule 15.10.2009

Ответы (8)


arrow_upward
2
arrow_downward

Если набор фиксирован, изучите идеальные хеш-функции.

person BCS    schedule 15.10.2009

arrow_upward
1
arrow_downward

По какой причине вы не можете написать свою собственную хэш-карту?

person Noon Silk    schedule 15.10.2009
comment
Прошло слишком много времени со времен колледжа, когда я написал свои собственные хеш-таблицы на C. Я даже не помню, как я это делал? Это был список с двусторонней связью? - person AngryHacker; 15.10.2009
comment
Написать так легко; В самом деле. Это займет у вас около часа. Хэш-карта - это просто список сегментов (списков), и все они помещаются в index % somePrime. Вы просто решаете, насколько велик ваш массив и сколько времени вы хотите потратить на поиск списков. - person Noon Silk; 15.10.2009

arrow_upward
1
arrow_downward

Это зависит от количества записей и вашего шаблона доступа.

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

Array.BinarySearch()
person Jan Bannister    schedule 15.10.2009

arrow_upward
0
arrow_downward

Что ж ... если вы хотите самую быструю и не слишком заботитесь о памяти, просто используйте две хеш-таблицы. Один идет в одну сторону, один идет в другую. Не уверен, есть ли способ более эффективно использовать память ...

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

person mpen    schedule 15.10.2009
comment
Для этого OP должен будет написать хеш-таблицу. - person BCS; 15.10.2009
comment
Разве он не может скачать его? В любом случае, написать хеш-таблицу не так уж и плохо. - person mpen; 15.10.2009

arrow_upward
0
arrow_downward

Разве это не так просто, как:

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

Я хотел бы сделать это как можно проще и просто перебирать массив, который вы ищете. Вы, вероятно, увидите выгоду от реализации некоторых процедур хеширования только в том случае, если ваш список (вычитает цифру из воздуха) более 1k + элементов, при этом дополнительная сложность ваших собственных процедур хеширования несколько замедляет работу.

person PaulG    schedule 15.10.2009

arrow_upward
0
arrow_downward

Несколько решений:

  1. Синхронизируйте 2 списка, выполняйте линейный поиск. Работает хорошо, если ваши коллекции не очень большие или вы не выполняете поиск постоянно.
  2. Две хэш-таблицы. Написать свой собственный довольно просто - это просто фиксированный массив сегментов (каждый сегмент может быть списком ArrayList). Сопоставьте элемент с корзиной, выполнив object.GetHashCode() % numBuckets.
  3. Два массива размером с диапазон значений. Если ваши числа находятся в фиксированном диапазоне, выделите массив размером этого диапазона с элементами из другой группы. Очень быстро и легко, но требует много памяти.
person dbkk    schedule 15.10.2009

arrow_upward
0
arrow_downward

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

person Ron Klein    schedule 15.10.2009

arrow_upward
0
arrow_downward

У меня была эта проблема несколько лет назад при программировании C, что нам нужно быстро найти штрих-код (числовой) примерно в 10 тысячах строк (в то время, используя файл в качестве базы данных - поскольку это было ручное устройство)

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

поиск 4050 в стеке 10000 элементов

начать с 5000 (10 000/2)
теперь, это число больше или меньше ... меньше

начать с 2500 (5000/2)
сейчас, это число больше или меньше ... выше

начните с 3750 (2500 + 2500/2)
теперь, это число больше или меньше ... выше

начать с 4375 (3750 + 1250/2)
теперь, это число больше или меньше ... меньше

начать с 4063 (4375 - 625/2)
теперь, это число больше или меньше ... меньше

начать с 3907 (4063 - 312/2)
сейчас, это число больше или меньше ... выше

начать с 3907 (3907 + 156/2)
сейчас, это число больше или меньше ... выше

начать с 3946 (3907 + 78/2)
сейчас, это число больше или меньше ... выше

...

пока вы не получите значение ... вам нужно будет выполнить поиск примерно 14 раз вместо 4050 итераций

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

Надеюсь, поможет

person balexandre    schedule 15.10.2009