ассоциативные массивы, или что-то что их заменяет Опции

[illusion21]

Добрый день.

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

Вроде бы на первый взгляд все просто, AppendIfUnique и FindItem через которые мы фильруем записи и находим нужный индекс если вдруг оказалось что такое значение уже было раньше записано. Но на практике получается ОЧЕНЬ медленный рассчет. По мере наполнения массива новыми данными скрипту приходится перебирать 2 раза все элементы массива чтобы проверить на уникальность и найти нужный индекс. В итоге при количестве записей равным 40к скрипт думает около минуты.. а при 150к мне вообще не удалось дождаться результата так как замедление работы происходит по наростающей с каждой новой записью.
Для проверки уникальности было бы здорово использовать ассоциативный массив в котором бы заносилась запись с именем равным самому значению и присвоением в это поле номер индекса под которым призошла запись в целевой массив..... например array["345334"]=50.. таким образом не пришлось бы перебирать все записи обычного массива а только попытаться обратиться к элементу с нужным именем. И проверка была бы простой, обращаемся к записи под нужным именем, если такая существует то берем ее значение и на этом задача решена.

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

[Lastjedi]

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

Искать дважды совсем не обязательно. Достаточно воспользоваться только функцией findItem.
например так:

Код

-- ValueArray - массив значений.
-- IndexArray - массив индексов.
-- newValue - новое значение.

local StoredValueIndex = findItem ValueArray newValue
if StoredValueIndex == 0 then (
    append ValueArray newValue
    append IndexArray ValueArray.count
)
else append IndexArray StoredValueIndex

Работает вполне прилично (в плане скорости).

[illusion21]

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

а про то что 2 раза не перебирать это точно.. как то я не подумал, спасибо

Сообщение отредактировал illusion21 - 24/12/2011, 21:04

[Lastjedi]

Вообще-то я имел в виду использование двух массивов. Не вижу смысла в отдельном массиве значений и массиве индексов, если значения имеют фактически тот же тип, что и индексы (integer).
А по поводу array["345334"]=50, как по твоему интерпретатор найдет в "ассоциативном" массиве запись с идентификатором "345334" если не перебором?

[[Vitus]]

Можно ещё попробовать такой вариант: свалить всё в один массив, отсортировать его, и переписать в новый, опуская дубликаты. Таким образом избавляемся от дорогой операции поиска в массиве на каждом добавлении. Но сортировка достаточно дорогая операция, хотя и однократная.

[illusion21]

Вообще-то я имел в виду использование двух массивов. Не вижу смысла в отдельном массиве значений и массиве индексов, если значения имеют фактически тот же тип, что и индексы (integer).
А по поводу array["345334"]=50, как по твоему интерпретатор найдет в "ассоциативном" массиве запись с идентификатором "345334" если не перебором?

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

[ECXIMER]

пробуй BigMatrix

[illusion21]

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

Сообщение отредактировал illusion21 - 24/12/2011, 21:53

[ECXIMER]

ну тогда bsearch() вместо finditem

[illusion21]

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

Или bsearch без сортировки умеет работать?

[ECXIMER]

не судьба )

[illusion21]

эх... ))
начал тут C# изучать чтобы max SDK юзать в дальнейшем.. сам по себе язык более чем понятен, а вот про практическое его применение для 3d max я пока не нашел хороших уроков. Не подскажете где их можно найти? так чтобы прям с нуля наглядно было объяснено как писать штуки именно с использованием max SDK?

[illusion21]

о блин. .оказывается SDK не поддерживает C#.. только С++

[Lastjedi]

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

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

Вдогонку пример:

Код

-- nSubArrays - Количество подмассивов, в которых будут сохраняться данные

local ArrayIndex = (mod newValue nSubArrays) as integer + 1

local StoredValueIndex = findItem ValueArray[ArrayIndex] newValue
if StoredValueIndex == 0 then (
    append ValueArray[ArrayIndex] newValue
    append IndexArray #(ArrayIndex, ValueArray[ArrayIndex].count)
)
else append IndexArray #(ArrayIndex, StoredValueIndex)

Чем больше общее количество значений, тем большее число массивов имеет смысл использовать. Например, если при количестве уникальных значений в 1 000 000, задать nSubArrays = 10000 заполнение происходит всего за несколько секунд.

Сообщение отредактировал Lastjedi - 25/12/2011, 09:03

[illusion21]

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

Сообщение отредактировал illusion21 - 25/12/2011, 10:00