|
|
|||||
Привести один массив к другому
Есть два массива (вектора), с одним работаем, другой служит как образец. Все элементы в каждом массиве могут встречаться только один раз. Необходимо "рабочий" массив сделать точно таким же, как образцовый, т.е. поменять местами некоторые элементы, некоторые добавить, некоторые удалить. На добавление/удаление при этом вызвать коллбек.
Сначала все удалить, потом по порядку добавить, ума много не надо. Но вот как реализовать все это красиво и в минимальное число проходов? Для примера: |
|
|||||
Для простого массива со строками или числами можно сделать рас:
или два второй способ вроде быстрее. Для сложных массивов (для массивов с массивами или массивов с объектами) адоб предлагает использовать следующую функцию: 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 |
|
|||||
Modus ponens
|
Вроде как.
Ну, или так: Возможно что-то выиграть от того, что удаляется не все содержание массива (меньше памяти "пачкается").
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 19.07.2013 в 01:24. |
|
|||||
|
|
|||||
[+1 25.10.13]
[+4 18.03.14] |
это вы ссылки приравняли
|
|
|||||
Ключевой момент тут:
Цитата:
Решение в лоб: сначала найти элементы одного, отсутствующие в другом, и наоборот, вызвать для каждого соответствующую функцию, потом уже изменить массив, но этого я хотел избежать. Ночью приснилось, как решить это рекурсивно. Вот что набросал на Питоне: 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] По-моему, это достаточно полезная функция, когда можно узнать, что именно изменять во вьюхе при произвольном изменении модели, вместо того, чтобы инициализировать все подряд. Последний раз редактировалось trashcoder; 22.07.2013 в 01:55. Причина: исправил код |
|
|||||
Регистрация: Nov 2010
Сообщений: 497
|
Ну начнем с того, что ваша программа некорректна.
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 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]. Это что? или Второй делается тоже просто. Просто начальный/конечный индексы в map нужно хранить и с ним работать. Первый делается гораздо сложнее (если с приемлемой сложностью). Там нужно уметь правильно пересчитывать "все" индексы за приемлемое время. При определенных ограничениях это вроде бы делается за NlogN (где N - количество оставшихся элементов). Там что-то вроде деревьев поиска "index -> количество предыдущих/следующих индексов" нужно строить. Это двоичное дерево с подсчетом в узле веса всего "поддерева". |
|
|||||
Modus ponens
|
Читайте про расстояния (Levenshtein distance, Hamming distance и т.д.)
Вам сначала нужно определится с тем, что именно вы хотите отследить, а потом уже это реализовывать. Например, в случае с заменами, как вы их отличите от перемещения? А если есть несколько одинаковых элементов? На эти вопросы нет однозначного ответа, нужно просто выбрать консистентую стратегию, и ей следовать.
__________________
Hell is the possibility of sanity |
|
|||||
Нужно было отследить элементы одного массива, отсутствующие в другом в обоих направлениях, а для тех, что есть в двух массивах, найти те, что имеют различные индексы, повторяющихся элементов при этом быть не должно по условию. Порядок вызовов onAdded/onRemoved/onMoved не важен. Затем привести массив к виду образца. Я искал, как сделать это все сразу, и в принципе, моя реализация выше (код исправил) этому соответствует. Другое дело, насколько этот подход оправдан и эффективен. Возможно, лучше действительно не городить огород, а последовательно сравнить индексы и изменить массив.
|
Часовой пояс GMT +4, время: 23:28. |
|
« Предыдущая тема | Следующая тема » |
Теги |
array , permutation , алгоритм |
|
|