Форум Flasher.ru - Привести один массив к другому

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Привести один массив к другому (http://www.flasher.ru/forum/showthread.php?t=202490)

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

Есть два массива (вектора), с одним работаем, другой служит как образец. Все элементы в каждом массиве могут встречаться только один раз. Необходимо "рабочий" массив сделать точно таким же, как образцовый, т.е. поменять местами некоторые элементы, некоторые добавить, некоторые удалить. На добавление/удаление при этом вызвать коллбек.
Сначала все удалить, потом по порядку добавить, ума много не надо. Но вот как реализовать все это красиво и в минимальное число проходов?
Для примера:

Код AS3:

const source:Array = [1, 9, 4, 3, 2, 100];

const target:Array = [4, 9, 2, 3, 1, 0];

syncTarget(source); // target = [1, 9, 4, 3, 2, 100], вызов onDelete(0), onAdd(100)

Для простого массива со строками или числами можно сделать рас:

Код AS3:

taget = source.slice();

или два

Код AS3:

taget = source.concat();

второй способ вроде быстрее.

Для сложных массивов (для массивов с массивами или массивов с объектами) адоб предлагает использовать следующую функцию:

Код AS3:

import flash.utils.ByteArray; 

 

function clone(source:Object):* 

{ 

    var myBA:ByteArray = new ByteArray(); 

    myBA.writeObject(source); 

    myBA.position = 0; 

    return(myBA.readObject()); 

}

Пруф ссылка на сайт с адобовским хелпом:
http://help.adobe.com/en_US/ActionSc...0204-7ee7.html

Проверка методов клонирования массивов на скорость:
http://flashlabs.wordpress.com/2009/...cat-or-slice0/
Если лень:
slice - 30ms
concat - 13ms
clone - 230ms

Код AS3:

target.splice.apply(target, [0, target.length].concat(source));

Код AS3:

target.length = 0;

target.push.apply(target, source);

Вроде как.

Ну, или так:

Код AS3:

target.length = source.length;

target.forEach(function (element: int, i: int, all: Array) { target[i] = source[i]; });

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

Код AS3:

target = source;

Один массив приравниваем к другому, но думаю вопрос здесь другой.

это вы ссылки приравняли

Ключевой момент тут:

Цитата:

Сообщение от trashcoder (Сообщение 1141403)

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

Нужно знать, какие элементы добавились, а какие удалились. Даже желательно еще узнать, какие поменяли индекс. Очистить, а затем заполнить массив я бы сумел (хоть и не додумался бы до решения в одну строку).
Решение в лоб: сначала найти элементы одного, отсутствующие в другом, и наоборот, вызвать для каждого соответствующую функцию, потом уже изменить массив, но этого я хотел избежать.
Ночью приснилось, как решить это рекурсивно. Вот что набросал на Питоне:

Код:

def added_handler(element, index):

    print("element '" + str(element) + "'\tadded at index", str(index))



def removed_handler(element, index):

    print("element '" + str(element) + "'\tremoved from index", str(index))



def moved_handler(element, index):

    print("element '" + str(element) + "'\tmoved to index", str(index))



def sync_arrays(source, target, on_added = None, on_removed = None, on_moved = None):

    def added(element, index):

        if on_added and element != None:

            on_added(element, index)



    def removed(element, index):

        if on_removed and element != None:

            on_removed(element, index)



    def moved(element, index):

        if on_moved and element != None:

            on_moved(element, index)



    def recursive_permutation(element):

        # element added

        if element in source and element not in target:

            index_in_source = source.index(element)

            added(element, index_in_source)

            replaced_by_element = target[index_in_source]

            target[index_in_source] = element

            recursive_permutation(replaced_by_element)

        # element removed

        elif element not in source and element in target:

            index_in_target = target.index(element)

            removed(element, index_in_target)

            replacing_element = source[index_in_target]

            recursive_permutation(replacing_element)

        # element moved

        elif element in source and element in target:

            index_in_source = source.index(element)

            index_in_target = target.index(element)

            if(index_in_source == index_in_target):

                return

            replaced_by_element = target[index_in_source]

            replacing_element = source[index_in_target]

            target[index_in_source] = element

            moved(element, index_in_source)

            if replaced_by_element == replacing_element:

                target[index_in_target] = replacing_element

                moved(replaced_by_element, index_in_target)

            else:

                recursive_permutation(replacing_element)

                recursive_permutation(replaced_by_element)



    # get rid of out of range error

    while len(target) < len(source):

        target.append(None)

    for i in range(0, len(source)):

        # all ok

        if target[i] == source[i]:

            continue

        # something different

        recursive_permutation(target[i])

    # remove rest garbage

    while i < len(target) - 1:

        removed(target.pop(), len(target))

    return target



if __name__ == "__main__":

    source = [18, 19, 1, 2, 4, 6, 8, 32, 3, 200, 42, 12, 99]

    target = [19, 18, 2, 3, 1, 8, 200, 12, 666, 32, 111, 222, 333, 444, 555]

    sync_arrays(source, target, added_handler, removed_handler, moved_handler)

    print("source", source)

    print("target", target)

Код кривоват, но результат удовлетворительный:

Код:

element '19'        moved to index 1

element '18'        moved to index 0

element '2'        moved to index 3

element '1'        moved to index 2

element '4'        added at index 4

element '3'        added at index 8

element '8'        moved to index 6

element '6'        added at index 5

element '200'        added at index 9

element '32'        added at index 7

element '12'        added at index 11

element '111'        removed from index 10

element '42'        added at index 10

element '333'        removed from index 12

element '99'        added at index 12

element '555'        removed from index 14

element '444'        removed from index 13

source [18, 19, 1, 2, 4, 6, 8, 32, 3, 200, 42, 12, 99]

target [18, 19, 1, 2, 4, 6, 8, 32, 3, 200, 42, 12, 99]

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

Ну начнем с того, что ваша программа некорректна.

Код:

    source = [18, 19, 1, 2, 4, 6, 8, 32, 3, 200, 42, 12, 99]

    target = [19, 18, 2, 3, 1, 8, 200, 12, 666, 32, 111, 222, 333, 444, 555]

...

RuntimeError: maximum recursion depth exceeded in cmp

В простейшем варианте все совсем просто. Конвертируем массивы в set, считаем, кто где добавился. Если не хочется set, можно отсортировать и пройтись по массиву.

Код:

def addedHandler(element):

    print("element '" + str(element) + "'\tadded")



def removedHandler(element):

    print("element '" + str(element) + "'\tremoved")



if __name__ == "__main__":

    source = [18, 19, 1, 2, 4, 6, 8, 32, 3, 200, 42, 12, 99]

    target = [19, 18, 2, 3, 1, 8, 200, 12, 666, 32, 111, 222, 333, 444, 555]

    sset = set(source)

    tset = set(target)

    for a in (tset - sset):

      addedHandler(a)

    for r in (sset - tset):

      removedHandler(r)

Если хочется с индексами, то нужно разобраться, что именно выводится. Это последовательность инструкций для построения последовательности или просто "какой индекс был, какой стал".

Ну допустим, есть [1, 2, 3] и [4, 3, 2]. Это что?

Код:

1 removed at 0

3 moved from 1 to 0

4 added at 0

или

Код:

1 removed at 0

3 moved from 2 to 1

2 moved from 1 to 2

4 added at 0

Второй делается тоже просто. Просто начальный/конечный индексы в map нужно хранить и с ним работать. Первый делается гораздо сложнее (если с приемлемой сложностью). Там нужно уметь правильно пересчитывать "все" индексы за приемлемое время. При определенных ограничениях это вроде бы делается за NlogN (где N - количество оставшихся элементов). Там что-то вроде деревьев поиска "index -> количество предыдущих/следующих индексов" нужно строить. Это двоичное дерево с подсчетом в узле веса всего "поддерева".

Читайте про расстояния (Levenshtein distance, Hamming distance и т.д.)
Вам сначала нужно определится с тем, что именно вы хотите отследить, а потом уже это реализовывать.
Например, в случае с заменами, как вы их отличите от перемещения? А если есть несколько одинаковых элементов? На эти вопросы нет однозначного ответа, нужно просто выбрать консистентую стратегию, и ей следовать.

Нужно было отследить элементы одного массива, отсутствующие в другом в обоих направлениях, а для тех, что есть в двух массивах, найти те, что имеют различные индексы, повторяющихся элементов при этом быть не должно по условию. Порядок вызовов onAdded/onRemoved/onMoved не важен. Затем привести массив к виду образца. Я искал, как сделать это все сразу, и в принципе, моя реализация выше (код исправил) этому соответствует. Другое дело, насколько этот подход оправдан и эффективен. Возможно, лучше действительно не городить огород, а последовательно сравнить индексы и изменить массив.