Комментарии 40
pack (M, [(all(M(i) /= V), i=1,size(M))])Чего только люди не выдумают, чтобы не писать вычисления на предписанном богом языке.
Это всё векторизуется.
А в Вашем алгоритме не учитывается случай, когда в массиве M несколько одинаковых чисел, подлежащих вычёркиванию. Если это, конечно, массив, а не множество.
Спасибо. Конечно, Вы правы. Интересно, кстати, было бы сравнить - какой алгоритм (Ваш или мой) быстрее справится с задачей, например, для n = 10^6, k = 2.
Можете попробовать на своём компьютере. У меня для этих параметров выполняется за 4 миллисекунды.
program exclude
implicit none
integer, allocatable :: M(:), V(:), N(:)
integer :: i
integer (8) :: t1, t2, rate
M = [(i, i=1,1000000)]
V = [4, 3]
call system_clock (t1)
N = pack (M, [(all(M(i) /= V), i=1,size(M))])
call system_clock (t2, rate)
print *, N
print *, "Time:", real(t2-t1,8)/rate
end program excludegfortran exclude.f90 -oexclude -O3 -ftree-vectorize -flto -fopt-info-vec -march=nativeНо для начала надо, чтобы программы делали одно и то же. То есть исключали повторяемые числа.
import time
# prepare data
n, k = 10**6, 2
M = set(range(1, n))
V = set(range(1, k))
# start timer
start = time.time()
# calculate
Z = M - V
# finish timer
end = time.time()
print("time:", end - start)
# print values < 12
print(list(filter(lambda v: v<12, Z)))
python3 main.py
time: 0.011850833892822266
[3, 4, 5, 6, 7, 8, 9, 10, 11]
11 мсек (ryzen 7600x), неплохо для питона, видно, что базовые операции хорошо оптимизированы.
При k не больше размера векторного регистра (т.е. в типовом современном случае для Intel – 8 или 16), это будет выполняться за O(n) векторных операций.
А можете расписать свои действия для случая M = {1, 2, 3, 4} V = {4, 1}?
Вас-то я и ждал! Спасибо! )) Значит, массив V тоже должен быть упорядочен.
Если массив V упорядочен, то можно что-то вроде операции слияния из сортировки слияния делать: сравниваем текущее число из M с текущим из V. Если меньшее в V, просто выбрасываем его. Если меньшее в M - выводим его в ответ. Если они равны, выбрасываем оба.
массив V тоже должен быть упорядочен.
M = [1, 2, 3, 4]
V = [2, 4]
результат 2 4 3 2
Кроме упорядоченности V необходимо на каждой итерации использовать swap:
t=M[j]
M[j]=M[V[j]]
M[V[j]]=t
Тогда, индексы из V передвинутся в начало массива M.
Вы можете доказать корректность алгоритма? Сомневаюсь в его работоспособности, даже если все числа в M и V различны.
уже доказали, пока я собирался))
https://habr.com/ru/articles/810327/comments/#comment_26760953
M = {1, 2, 3, 4}; V = {3, 1}
M[1] = V[1] = 3, M[V[1]] = M[3] = 1; M = {3, 2, 1, 4}
M[2] = V[2] = 1, M[V[2]] = M[1] = 2; M = {2, 1, 1, 4}
Хвост {1, 4}. Ошибка.
Да, массив V надо упорядочить. Я ошибался. Спасибо.
M = {1, 2, 3, 4}; V = {2, 3}
M[1] = V[1] = 2, M[V[1]] = M[2] = 1; M = {2, 1, 3, 4}
M[2] = V[2] = 3, M[V[2]] = M[3] = 2; M = {2, 3, 2, 4}
Хвост {2, 4}. Ошибка.
Могли бы и сами проверить свой гениальный алгоритм. Для |M| = 4 и |V| = 2 всего-то 12 вариантов надо перебрать.
Вторая помена должна поменять местами M[2] и M[3].
Это действительно работает. Поддерживается инвариант, что первые j элементов массива M содержат элементы из начала запрещенного массива V[1..j]. А элементы больше максимального V[1..j] не тронуты (M[i] = i, i > max(V[k] | k <= j)).
На каждой следующей итерации, поскольку V упорядочен, то V[j] >= j и M[v[j]] = j (по инварианту с предыдущей итерации). Поменяв местами M[v[j]] и M[j] мы восстановим инвариант: На индексах < j стоят вычеркнутые числа еще с предыдущей итерации. Вот тут мы в j-ый индекс поместили v[j]. Так же, мы испортили лишь v[j]-ый элемент, а значит все более правые элементы в массиве М все еще равны индексам.
Может и должна, но по алгоритму, предложенному автором, не меняет.
Вместо авторского M[j] = V[j]; M[V[j]] = j; должна быть [M[j], M[V[j]]] = [M[V[j]], M[j]]
Ну, автор же не на каком-то языке программирования писал. Это псевдокод. И словами описал это именно "перестановки". Не совсем точно описано, да, можно прочитать двояко.
Нет, у автора во втором выражении присваивается именно индекс, а не значение элемента по индексу.
У автора ничего не присваивается. У автора написано M[j] = V[j], M[V[j]] = j
Вы интерпретировали это как две последовательные операции присваивания. Автор же имел ввиду одну операцию: перестановку M[j] и M[V[j]]. Это понятно из контекста.
@MarkNest советую вам это в тексте подправить. Можно написать что-то вроде:M[j], M[V[j]] = M[V[j]], M[j]илиswap(M[j], M[V[j]]).
да описался я! Сейчас исправлю. Спасибо, что не даете писать глупости))
У вас уже есть массив M размера N, значит N не очень большое. Тогда можно в битовом массиве размера N пометить все числа из K, потом все числа из M выводить в ответ, если битовой пометки нет.
Это работает и для неупорядоченного массива K, в отличии от вашего алгоритма. Если вам медленно аллокации, то можно делать пометки прямо в массиве M в каких-нибудь старших битах (например, знак менять у чисел).
Если же и N и K очень большие, то можно использовать хеш-таблицу для пометок.
Отдельное спасибо за КДПВ. Сами рисовали?
Насколько я понял, с поправками работает, если V упорядоченный. А если нет? Интересно, тогда можно допилить?
Отсортировать, ха-ха.
Кажется, за O(k), да с константной памятью (без хаков вроде использования лишних битов в M[]) - никак.
Ну, допустим, у нас такой алгоритм есть. А мы берем и последнее число в V[] произвольно меняем. Это значит, что алгоритм должен за константное количество операций найти это число в как-то перемешанном массиве M. Причем подбирая предыдущие числа в V мы можем очень сильно влиять на то, как массив перемешан. Кажется, это невозможно.
Очень бы хотелось, но, кажется, @wataru прав. Единственная надежда: упорядочивание V - это слишком строгое условие (иногда ведь перестановки срабатывают и без упорядочивания) - надежда очень слабая.
Тоже сначала не понял с этими индексами и перестановками.
Получается так:
Для каждого значения V, найти индекс значения в массиве M.
В M итеративно переставить местами элементы на найденные индексы.
Получившийся массив разделить на размер V, правая часть будет решением.
Работает без сортировки, код на js:
function alg(M, V) {
const len = V.length;
for (let k = 0; k < len; k++) {
// берем значение из M
const iterationValue = M[k],
// берем значение из V
valV = V[k],
// ищем V индекс в M
index = M.indexOf(valV);
// меняем местами элементы(swap)
M[k] = valV;
M[index] = iterationValue;
}
// 3. делим массив на длину V и возвращаем правую часть
return M.slice(len);
}
alg([1, 2, 3, 4], [4, 1]);
// Array [ 3, 2 ]
alg([1, 2, 3, 4], [1, 4]);
// Array [ 3, 2 ]
alg([1, 2, 3, 4], [3, 4]);
// Array [ 1, 2 ]
alg([1, 2, 3, 4], [2, 1]);
// Array [ 3, 4 ]
alg([3, 5, 4, 2, 8], [5, 2]);
// Array(3) [ 4, 3, 8 ]
alg([1, 2, 3, 4], [2, 4]);
// Array [ 3, 1 ]
«А» и «Б» сидели на трубе. «А» упало, «Б» пропало. Что осталось на трубе? (алгоритм получения ответа в частном случае)