Как оптимизировать поисковую разницу между массивом / списком объектов

Question

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

Давайте предположим, что у меня есть два списка элементов A и B (без повторяющихся значений), и мне нужно сравнить их и удалить все элементы, присутствующие в обоих, так что в конце я должен иметь

• в A все элементы, которые находятся в A, но не в B
• в B все элементы, которые находятся в B, но не в A

теперь я делаю что-то подобное:

            for (var i:int = 0 ; i < a.length ;)
            {
                var isFound:Boolean = false;
                for (var j:int = 0 ; j < b.length ;)
                {
                    if (a.getItemAt(i).nome == b.getItemAt(j).nome)
                    {
                        isFound = true;
                        a.removeItemAt(i);
                        b.removeItemAt(j);
                        break;
                    }
                    j++;
                }
                if (!isFound)
                    i++;
            }

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

Мне было интересно, если (и я уверен, что есть) есть лучший (и менее потребляющий процессор) способ сделать это...

Answer 1

Если вам нужно использовать список, и вам не нужны возможности arraycollection, я предлагаю просто преобразовать его в использование векторов AS3. Увеличение производительности в соответствии с этим (http://www.mikechambers.com/blog/2008/09/24/actioscript-3-vector-array-performance-comparison/) составляет 60% по сравнению с массивами. Я считаю, что массивы уже в 3 раза быстрее, чем ArrayCollections из какой-то статьи, которую я когда-то читал. К сожалению, это решение все еще O(n^2) во времени.

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

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

Если вы хотите сделать НАМНОГО быстрее, чем это, используйте ассоциативный массив (объект в as3). Конечно, это может потребовать больше усилий по рефакторингу. Я предполагаю, что object.nome является уникальной строкой / идентификатором для объектов. Просто назначьте это значение nome в качестве ключа в objectA и objectB. Делая это таким образом, вам может не потребоваться циклически проходить по каждому элементу в каждом списке для сравнения.