Поиск в многомерном массиве

[udaaff]

Не, данные продолжают добавляться как и прежде, но при этом в отдельном двумерном массиве ты фиксируешь уже то, что было добавлено, отмечая ячейку (true записываешь, например), данные убрал - true удалил. Т.е. если в массиве/карте по адресу (2;3) уже true, то данные в очередь не вносятся.

[wvxvw]

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

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

[Nooob]

у тебя же уже есть один числовой парметр - это индекс в массиве первого уровня, зачем в массиве второго уровня хранить его? в твоём случае это вполне себе одномерный массив [1, 2, 3]

[Psycho Tiger]

[offtop] Мне очень нравится, как wxvxw отвечает на простые вопросы. Over-qualification в действии [/offtop]

[GBee]

[offtop] Мне очень нравится, как wxvxw отвечает на простые вопросы. Over-qualification в действии [/offtop]

:о)) Ага, проблема? Попробуйте построить ракету и взглянуть на проблему с орбиты.

[wvxvw]

Да почему ракету? Упорядоченые или частично упорядоченые коллекции были известны человечеству задолго до моего рождения. Во многих популярных языках они входят в стандартную библиотеку. В ЭкшнСркипте их нет в стандартной библиотеке, но есть на просторах интернета: я встречал как минимум две реализации кучи.

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

Блум фильтры - это общий случай хеш таблицы, который просто самому написать, но это уже по желанию.

[ZackMercury]

В ЭкшнСркипте их нет в стандартной библиотеке, но есть на просторах интернета: я встречал как минимум две реализации кучи.

Класса-посредника, который содержит в себе массив и манипулирует его свойствами и методами? Это может быть быстрее, чем общение с массивом напрямую? Не верю. Докажите.

[wvxvw]

Я не совсем понимаю, что нужно доказывать? Что поиск в куче будет быстрее поиска в массиве? Ну так это в любом пособии для начинающих по структурам данных говорится... Поиск по неупорядоченому массиву: O(n), поикс в куче: O(log n). Тут как бы к гадалке не ходи... Куча примечательна еще и тем, что константа рядом с log n очень маленькая, т.как обычно сохраняется в массив, а рассчет индекса в массиве делается с помощью побитовых сдвигов.