Обновление массива с учетом расположения элементов

[Silentland]

Массив уникальных айдишников:
[1, 4, 32, 2, 5, 7, 8]

обновленный массив (содержащий незначительные отличия от исходного):
[4, 8, 17, 32, 2, 7, 9, 3]

Нужно, используя стандартные функции работы с массивами push, pop, shift, unshift, splice, преобразовать первый массив во второй наиболее быстрым способом изменяя как можно меньше элементов. Отличия между массивами, как правило, в нескольких элементах. Массивы доступны для чтения без ограничений.

Существуют ли готовые алгоритмы? Ваш вариант?

 

[ksnk]

Это что, задача на зачет? Спортивное программирование или реальная задача? Для реальной задачи в ней маловато реальности.
Что на само деле нужно сделать и откуда взялись эти массивы?

 

[Silentland]

push, pop, shift, unshift, splice это функции стороннего js-плагина, внутрь которого зашит первый массив (прямого доступа у нас к нему нет). Задача в том, чтобы с помощью этих функций преобразовать внутренний первый массив к виду второго, так, чтобы не трогать совпадающие элементы, чтобы они не рендерились лишний раз.

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

P.S. Думаю, можно обойтись и одной splice для упрощения

 

[hell0w0rd]

а браузер и так и так вроде будет рендрить все заново

 

[Adelf]

Я знаю как.

arr.pop();
arr.pop();
arr.pop();
arr.pop();
arr.pop();
arr.pop();
arr.pop();

arr.push(4);
arr.push(8);
arr.push(17);
arr.push(32);
arr.push(2);
arr.push(7);
arr.push(9);
arr.push(3);

Какой вопрос - такой ответ.

 

[Silentland]

а браузер и так и так вроде будет рендрить все заново

Не будет. По крайней мере, это будет какой-то поверхностный, не заметный глазу рендер, в отличие от вставки всего списка с помощью append

Какой вопрос - такой ответ.

Это называется придираться к словам. Не умно, не умно...

 

[Adelf]

Silentland
Это не придирка к словам. Это попытка донести, что ты неправильно формулируешь задачу. Вспомни школьную физику.
Давай попробую за тебя.
Дано: Два массива. Исходный и результатный.
Необходимо: программно рассчитать алгоритм, позволяющий за минимальное количество вышеописанных операций привести исходный к результатному - так?

 

[Silentland]

Необходимо: программно рассчитать алгоритм, позволяющий за минимальное количество вышеописанных операций привести исходный к результатному - так?

Ну это же не учебник физики и не задача из разряда от чего утка плавает. Все поняли смысл, в том числе и вы, так что это просто был стёб, признайтесь)

Необходимо просто рассчитать алгоритм (хотите программно, хотите в уме), использующий указанные функции. Позволяющий за минимальное время преобразовать массив. Условия не четкие, но такая уж жизнь, редко ставит четкие условия. Предположим, что pop, push самые быстрые операции, shift, unshift медленнее, а splice самая медленная, но единственная, которая работает с набором элементов. Давайте обойдемся последней для упрощения. Тогда задача сведется к тому, чтобы подготовить набор параметров для splice и запускать эту функцию минимальное количество раз.

P.S. В учебнике математики было бы написано преобразовать массив [a1, a2, ... , an] к виду [b1, b2, ... bm], где... Я бы 20 мин вспоминал как перевести на математический язык, а все бы 20 мин. расшифровывали обратно)

 

[AmdY]

Переношу в корзину, пока не появится условия.

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

 

[Adelf]

AmdY
Не. Все верно сейчас. Задача ясная.
Связи между массивами нет. Нужно лишь превратить один в другой минимальными усилиями. Перенеси обратно

Upd: Перенес в Теорию.

 

[Silentland]

Дополните тогда уж тему «Прочтите ПЕРЕД тем, как писать в этот форум». Примерчик там набросайте как оформлять задачи. Я ж не против))

На всякий случай, уточнил, что массивы доступны для чтения. Но изменять можно только указанными функциями

 

[С.]

Не. Все верно сейчас. Задача ясная.
Связи между массивами нет. Нужно лишь превратить один в другой минимальными усилиями.

А мне все равно не ясна практическая суть задачи. Один в другой минимальными усилиями превращается операцией присвоения/копирования.

 

[Adelf]

С.
Да в общем то неважно. Поместил в Теорию. Практической части может и не быть. Вполне сносная задачка на теорию.

Вообще я такую решал уже. Абсолютно такую же задачу решает любой diff/merge в системах хранения сорцов. Подозреваю, что тебе необзательно найти самое оптимальное.. желательно лишь приемлимое решение. Чтобы если массивы реально похожи - было мало операций.

Самый простой вариант:
Идем по результатному массиву. И пытаемся строить его из кирпичиков исходного.
Главное - не идти в поисках нужного элемента в исходном слишком глубоко.
Либо другой вариант - строить дерево решений(каждый раз выбирая - либо найти в исходном этот элемент, либо вставить с нуля). И выбрать из них оптимальный. Весь вопрос - а сколько долго можно искать алгоритм? Если долго, то можно и перебрать много вариантов. если нет - то идти путем попроще.

 

[Silentland]

А мне все равно не ясна практическая суть задачи. Один в другой минимальными усилиями превращается операцией присвоения/копирования.

Нужно свести задачу рендеринга к минимуму. Если мы удаляем из массива [0, 1, 2] элемент 1, превращая массив в [0, 2], этому соответствует операция
$('arr').children().eq(1).remove() (на языке jQuery).

Если мы очищаем и перезаписываем массив, этому будет соответствовать что-то вроде
$('arr').empty()
$('arr').append([0, 2])
(при большом количестве элементов заметно мерцание)

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

 

[флоппик]

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

 

[С.]

Нужно свести задачу рендеринга к минимуму. Если мы удаляем из массива [0, 1, 2] элемент 1, превращая массив в [0, 2], этому соответствует операция
$('arr').children().eq(1).remove() (на языке jQuery).

Если ты знаешь последовательность действий, то и следуй ей. При чем здесь задача нахождения [возможных] действий между двумя состояниями?

Если ты не занешь последовательность действий, но имеешь итоговое состояние, то просто перерисовывай все и не мни мозги.

 

[Silentland]

Идем по результатному массиву. И пытаемся строить его из кирпичиков исходного.

Вот тут возникает такая штука как циклическое сравнение каждого элемента одного массива с каждым элементом другого. Т.е. сложность O(N). От этого и хотелось бы избавиться. Есть же алгоритмы сортировки для структур с небольшими изменениями... Тут тоже своего рода сортировка, но не по алфавиту, а по другому массиву.

 

[Silentland]

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

Не могу я ничего клонировать. Доступ к DOM у стороннего плагина, я лишь могу пользоваться его АПИ

 

[Adelf]

Вот тут возникает такая штука как циклическое сравнение каждого элемента одного массива с каждым элементом другого. Т.е. сложность O(N).

Во-первых О(N^2).
Во-вторых это в самом худшем случае. В реально близких массивах - будет О(N).
В-третьих скажи какой примерно размер массивов. если маленькие, то вообще плевать на О.

 

[Silentland]

Во-первых О(N^2).

Сорри ошибся. Верно О(N^2)

Во-вторых это в самом худшем случае. В реально близких массивах - будет О(N).

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

В-третьих скажи какой примерно размер массивов. если маленькие, то вообще плевать на О.

Несколько сотен элементов... До тысячи, думаю.