Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 18.07.2013, 23:39
trashcoder вне форума Посмотреть профиль Отправить личное сообщение для trashcoder Найти все сообщения от trashcoder
  № 1  
Ответить с цитированием
trashcoder

Регистрация: Jul 2012
Сообщений: 10
Записей в блоге: 1
По умолчанию Привести один массив к другому

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

Старый 19.07.2013, 00:38
KumoKairo вне форума Посмотреть профиль Отправить личное сообщение для KumoKairo Найти все сообщения от KumoKairo
  № 2  
Ответить с цитированием
KumoKairo
 
Аватар для KumoKairo

Регистрация: Jan 2013
Сообщений: 550
Записей в блоге: 1
Для простого массива со строками или числами можно сделать рас:
Код 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

Старый 19.07.2013, 01:13
wvxvw вне форума Посмотреть профиль Отправить личное сообщение для wvxvw Найти все сообщения от wvxvw
  № 3  
Ответить с цитированием
wvxvw
Modus ponens
 
Аватар для wvxvw

модератор форума
Регистрация: Jul 2006
Адрес: #1=(list #1#)
Сообщений: 8,049
Записей в блоге: 38
Код 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]; });
Возможно что-то выиграть от того, что удаляется не все содержание массива (меньше памяти "пачкается").
__________________
Hell is the possibility of sanity


Последний раз редактировалось wvxvw; 19.07.2013 в 01:24.
Старый 19.07.2013, 13:57
Bletraut вне форума Посмотреть профиль Отправить личное сообщение для Bletraut Найти все сообщения от Bletraut
  № 4  
Ответить с цитированием
Bletraut
 
Аватар для Bletraut

Регистрация: Mar 2013
Адрес: Вне пространства.
Сообщений: 566
Отправить сообщение для Bletraut с помощью ICQ Отправить сообщение для Bletraut с помощью Skype™
Код AS3:
target = source;
Один массив приравниваем к другому, но думаю вопрос здесь другой.

Старый 19.07.2013, 14:05
Babylon вне форума Посмотреть профиль Отправить личное сообщение для Babylon Посетить домашнюю страницу Babylon Найти все сообщения от Babylon
  № 5  
Ответить с цитированием
Babylon
[+1 25.10.13]
[+4 18.03.14]
 
Аватар для Babylon

Регистрация: Jan 2006
Адрес: Москва, Зеленоград
Сообщений: 653
Отправить сообщение для Babylon с помощью ICQ
это вы ссылки приравняли

Старый 19.07.2013, 17:08
trashcoder вне форума Посмотреть профиль Отправить личное сообщение для trashcoder Найти все сообщения от trashcoder
  № 6  
Ответить с цитированием
trashcoder

Регистрация: Jul 2012
Сообщений: 10
Записей в блоге: 1
Ключевой момент тут:
Цитата:
Сообщение от trashcoder Посмотреть сообщение
На добавление/удаление при этом вызвать коллбек. Сначала все удалить, потом по порядку добавить, ума много не надо.
Нужно знать, какие элементы добавились, а какие удалились. Даже желательно еще узнать, какие поменяли индекс. Очистить, а затем заполнить массив я бы сумел (хоть и не додумался бы до решения в одну строку).
Решение в лоб: сначала найти элементы одного, отсутствующие в другом, и наоборот, вызвать для каждого соответствующую функцию, потом уже изменить массив, но этого я хотел избежать.
Ночью приснилось, как решить это рекурсивно. Вот что набросал на Питоне:
Код:
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 и буду дальше дорабатывать напильником, но вопрос о лучшем и самом быстром решении остается в силе.
По-моему, это достаточно полезная функция, когда можно узнать, что именно изменять во вьюхе при произвольном изменении модели, вместо того, чтобы инициализировать все подряд.


Последний раз редактировалось trashcoder; 22.07.2013 в 01:55. Причина: исправил код
Старый 19.07.2013, 17:30
maxkar вне форума Посмотреть профиль Отправить личное сообщение для maxkar Найти все сообщения от maxkar
  № 7  
Ответить с цитированием
maxkar

Регистрация: 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
В простейшем варианте все совсем просто. Конвертируем массивы в 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 -> количество предыдущих/следующих индексов" нужно строить. Это двоичное дерево с подсчетом в узле веса всего "поддерева".

Старый 19.07.2013, 19:14
wvxvw вне форума Посмотреть профиль Отправить личное сообщение для wvxvw Найти все сообщения от wvxvw
  № 8  
Ответить с цитированием
wvxvw
Modus ponens
 
Аватар для wvxvw

модератор форума
Регистрация: Jul 2006
Адрес: #1=(list #1#)
Сообщений: 8,049
Записей в блоге: 38
Читайте про расстояния (Levenshtein distance, Hamming distance и т.д.)
Вам сначала нужно определится с тем, что именно вы хотите отследить, а потом уже это реализовывать.
Например, в случае с заменами, как вы их отличите от перемещения? А если есть несколько одинаковых элементов? На эти вопросы нет однозначного ответа, нужно просто выбрать консистентую стратегию, и ей следовать.
__________________
Hell is the possibility of sanity

Старый 22.07.2013, 02:10
trashcoder вне форума Посмотреть профиль Отправить личное сообщение для trashcoder Найти все сообщения от trashcoder
  № 9  
Ответить с цитированием
trashcoder

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

Создать новую тему Ответ Часовой пояс GMT +4, время: 14:12.
Быстрый переход
  « Предыдущая тема | Следующая тема »  

Теги
array , permutation , алгоритм
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 14:12.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.