25.04.2024 07:21
MarkNest 40 2600 Источник

Началось всё с того, что не нашел я библиотеки для JavaScript, которая вычисляет собственные векторы для комплекснозначной матрицы 4х4. Пришлось писать самому.

И в ходе реализации встала передо мной этакая бодренькая микрозадачка – из набора чисел «1, 2, 3, 4» вычеркнули два числа «x, y» (неодинаковых – кто-то придет завтра и задаст эти два числа, а мы сегодня должны приготовиться), требуется объяснить компьютеру, как определить оставшиеся, невычеркнутые числа. И я завис – все идеи, которые приходили мне в голову, казались «неспортивными и чрезмерными» – ну не пузырьковой же сортировкой перебирать четыре числа, должно же быть что-то элегантное. Например, если вычеркнуто не два, а три числа «x, y, z» из четырех «x, y, z, t» (которые «1, 2, 3, 4»), то оставшееся число «t» находится так: t = 10 – (x+y+z). Потому что t+x+y+z = 10 (всегда: 10=1+2+3+4). Вполне элегантно для одного оставшегося числа. А для двух чисел – как быть с элегантностью?!

Решение я нашел – озарило по дороге домой – прям шарахнуло с неба по башке; я даже не поверил сначала, что это оно – показалось мороком усталого мозга. И оно работает не только для четырех чисел – можно решить задачу «из n последовательных чисел вычеркнуто k различных чисел, требуется вернуть остаток» (что осталось на трубе).

Я предложил эту задачку с «n, k»-условием знакомым программистам в качестве застольного анекдота, для развлечения (сам я не программист, честно – мне просто сильно занадобилось объяснить Яваскрипту, как вычислять собственные векторы комплекснозначной матрицы 4х4). Сначала я выслушал их предложения (предлагали «упорядочивание k чисел с последующим перебором n чисел» и «воспользоваться встроенной функцией вычитания множеств»). Потом я рассказал свое решение. Они сказали: «Ну круто, да».

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

Постановка задачи

Есть массив M[i] = i, при i = 1 … n. Числа, которые надо вычеркнуть из массива M, находятся в массиве V. Массив V: размером k, числа в этом массиве не повторяются и не обязательно упорядочены (upd: массив V должен быть упорядочен). Требуется вернуть массив невычеркнутых чисел. 

Алгоритм (upd)

- Перестановки в массиве М:
M[1] <--> M[ V[1] ]
M[2] <--> M[ V[2] ]
...
M[k] <--> M[ V[k] ]
Всего k перестановок.

- Невычеркнутые числа теперь находятся в хвосте массива M:
M[(k+1), n] (этот хвост и вернуть).

 Пример действия алгоритма (n=4, k=2)

M = {1, 2, 3, 4},
Задаем V = {4, 3}. (в хвосте после перестановок ожидаем числа: «1» и «2»)

Перестановки:
M[1] <--> M[4]; (теперь M = {4, 2, 3, 1}),
M[2] <--> M[3]; (теперь M = {4, 3, 2, 1}).
Хвост массива M: M[3,4] = {2, 1} – то, что нужно.

 Пример применения в жизни

Вот это я и заюзал, когда объяснял компу, как надо решать систему линейных уравнений методом Гаусса.

 Сам код разместил на GitHub пользователь Хабра Сергей (за что ему огромное спасибо) Благодаря ему можно показать код, где это использовано:
функция «zMatrix_minus_lambda_SV» (напр., строки: 266-267).

А надо всё это мне было, чтобы написать калькулятор «Прашкевич», который строит спектры поглощения и отражения света стопкой пластин.

 Ссылки:
- Прашкевич на Бегете
- Прашкевич на GitHub
- Статья с описанием Прашкевича (зачем и почему)
- Юмористический рассказ «Как неофит познавал яваскрипт» (как я страдал)

 Конец.

Комментарии (40)


  1. vadimr
    25.04.2024 07:48
    #26760279
    +1

    pack (M, [(all(M(i) /= V), i=1,size(M))])

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

    Это всё векторизуется.

    А в Вашем алгоритме не учитывается случай, когда в массиве M несколько одинаковых чисел, подлежащих вычёркиванию. Если это, конечно, массив, а не множество.


    1. MarkNest Автор
      25.04.2024 07:48
      #26760325

      Спасибо. Конечно, Вы правы. Интересно, кстати, было бы сравнить - какой алгоритм (Ваш или мой) быстрее справится с задачей, например, для n = 10^6, k = 2.


      1. vadimr
        25.04.2024 07:48
        #26760373
        +1

        Можете попробовать на своём компьютере. У меня для этих параметров выполняется за 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 exclude
        gfortran exclude.f90 -oexclude -O3 -ftree-vectorize -flto -fopt-info-vec -march=native

        Но для начала надо, чтобы программы делали одно и то же. То есть исключали повторяемые числа.


        1. AcckiyGerman
          25.04.2024 07:48
          #26760715

          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), неплохо для питона, видно, что базовые операции хорошо оптимизированы.


          1. vadimr
            25.04.2024 07:48
            #26760745

            Просили-то из массива исключать, а не из множества. Для множества это вообще элементарная операция.


        1. vadimr
          25.04.2024 07:48
          #26760723

          При k не больше размера векторного регистра (т.е. в типовом современном случае для Intel – 8 или 16), это будет выполняться за O(n) векторных операций.


          1. MarkNest Автор
            25.04.2024 07:48
            #26761309

            O(n) или O(k)?


            1. vadimr
              25.04.2024 07:48
              #26761325

              O(n). Нам же всё равно надо весь большой массив перебрать.

              А без векторизации будет O(n*k).


              1. MarkNest Автор
                25.04.2024 07:48
                #26761347

                Спасибо, понял.


  1. xi-tauw
    25.04.2024 07:48
    #26760291
    +2

    А можете расписать свои действия для случая M = {1, 2, 3, 4} V = {4, 1}?


    1. MarkNest Автор
      25.04.2024 07:48
      #26760675

      Вас-то я и ждал! Спасибо! )) Значит, массив V тоже должен быть упорядочен.


      1. wataru
        25.04.2024 07:48
        #26760783
        +1

        Если массив V упорядочен, то можно что-то вроде операции слияния из сортировки слияния делать: сравниваем текущее число из M с текущим из V. Если меньшее в V, просто выбрасываем его. Если меньшее в M - выводим его в ответ. Если они равны, выбрасываем оба.


      1. Alexandroppolus
        25.04.2024 07:48
        #26760795

        массив V тоже должен быть упорядочен.

        M = [1, 2, 3, 4]

        V = [2, 4]

        результат 2 4 3 2


        1. MarkNest Автор
          25.04.2024 07:48
          #26761173

          Спасибо, что не даете мне писать глупости. Алгоритм работает, в описании у меня ошибка (сейчас исправлю).

          M[1] <--> M[2]: M = {2,1,3,4}
          M[2] <--> M[4]: M = {2,4,3,1}
          результат: 3,1


      1. jusd
        25.04.2024 07:48
        #26760943

        Кроме упорядоченности V необходимо на каждой итерации использовать swap:

        t=M[j]

        M[j]=M[V[j]]

        M[V[j]]=t

        Тогда, индексы из V передвинутся в начало массива M.


        1. MarkNest Автор
          25.04.2024 07:48
          #26761181

          да! Спасибо. Я сегодня сам не свой... Сейчас исправлю.


  1. jusd
    25.04.2024 07:48
    #26760371
    +2

    Вы можете доказать корректность алгоритма? Сомневаюсь в его работоспособности, даже если все числа в M и V различны.


    1. MarkNest Автор
      25.04.2024 07:48
      #26761231

      уже доказали, пока я собирался))
      https://habr.com/ru/articles/810327/comments/#comment_26760953


  1. Rsa97
    25.04.2024 07:48
    #26760431
    +2

    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}. Ошибка.


    1. MarkNest Автор
      25.04.2024 07:48
      #26760683

      Да, массив V надо упорядочить. Я ошибался. Спасибо.


      1. Rsa97
        25.04.2024 07:48
        #26760905
        +2

        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 вариантов надо перебрать.


        1. wataru
          25.04.2024 07:48
          #26760953
          +1

          Вторая помена должна поменять местами 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]-ый элемент, а значит все более правые элементы в массиве М все еще равны индексам.


          1. Rsa97
            25.04.2024 07:48
            #26760983
            +1

            Может и должна, но по алгоритму, предложенному автором, не меняет.
            Вместо авторского M[j] = V[j]; M[V[j]] = j; должна быть [M[j], M[V[j]]] = [M[V[j]], M[j]]


            1. wataru
              25.04.2024 07:48
              #26761025
              +2

              Ну, автор же не на каком-то языке программирования писал. Это псевдокод. И словами описал это именно "перестановки". Не совсем точно описано, да, можно прочитать двояко.


              1. Rsa97
                25.04.2024 07:48
                #26761037
                +2

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


                1. wataru
                  25.04.2024 07:48
                  #26761109
                  +2

                  У автора ничего не присваивается. У автора написано 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]]).


                  1. Rsa97
                    25.04.2024 07:48
                    #26761133
                    +1

                    Но и дальше в примерах видим то самое присвоение j.

                    M[1] = V[1] = 4, M[V[1]]= M[4] = 1; (теперь M = {4, 2, 3, 1}),
                    Так что непонятно, где именно вы нашли "контекст, из которого понятно".


                    1. vadimr
                      25.04.2024 07:48
                      #26761257

                      Ну ясно по логике, что там надо делать. Что индекс сам по себе никуда не впёрся.


                  1. MarkNest Автор
                    25.04.2024 07:48
                    #26761251

                    Спасибо! )) Впредь буду долго думать, перед тем, как написать.


                1. MarkNest Автор
                  25.04.2024 07:48
                  #26761183

                  да описался я! Сейчас исправлю. Спасибо, что не даете писать глупости))


  1. wataru
    25.04.2024 07:48
    #26760797
    +2

    У вас уже есть массив M размера N, значит N не очень большое. Тогда можно в битовом массиве размера N пометить все числа из K, потом все числа из M выводить в ответ, если битовой пометки нет.

    Это работает и для неупорядоченного массива K, в отличии от вашего алгоритма. Если вам медленно аллокации, то можно делать пометки прямо в массиве M в каких-нибудь старших битах (например, знак менять у чисел).

    Если же и N и K очень большие, то можно использовать хеш-таблицу для пометок.


    1. MarkNest Автор
      25.04.2024 07:48
      #26761189

      Спасибо!


  1. wataru
    25.04.2024 07:48
    #26761469
    +2

    Отдельное спасибо за КДПВ. Сами рисовали?


    1. MarkNest Автор
      25.04.2024 07:48
      #26763333

      Вам спасибо за оценку))) Я не рисовал, но я старался выбрать получше.


  1. Alexandroppolus
    25.04.2024 07:48
    #26761557
    +1

    Насколько я понял, с поправками работает, если V упорядоченный. А если нет? Интересно, тогда можно допилить?


    1. wataru
      25.04.2024 07:48
      #26761669
      +1

      Отсортировать, ха-ха.

      Кажется, за O(k), да с константной памятью (без хаков вроде использования лишних битов в M[]) - никак.

      Ну, допустим, у нас такой алгоритм есть. А мы берем и последнее число в V[] произвольно меняем. Это значит, что алгоритм должен за константное количество операций найти это число в как-то перемешанном массиве M. Причем подбирая предыдущие числа в V мы можем очень сильно влиять на то, как массив перемешан. Кажется, это невозможно.


    1. MarkNest Автор
      25.04.2024 07:48
      #26763335

      Очень бы хотелось, но, кажется, @wataru прав. Единственная надежда: упорядочивание V - это слишком строгое условие (иногда ведь перестановки срабатывают и без упорядочивания) - надежда очень слабая.


      1. MarkNest Автор
        25.04.2024 07:48
        #26763417

        ...


  1. ALapinskas
    25.04.2024 07:48
    #26762157
    +1

    Тоже сначала не понял с этими индексами и перестановками.

    Получается так:

    1. Для каждого значения V, найти индекс значения в массиве M.

    2. В M итеративно переставить местами элементы на найденные индексы.

    3. Получившийся массив разделить на размер 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 ]


    1. wataru
      25.04.2024 07:48
      #26762327
      +1

      Ваш метод сильно медленнее. Он работает за O(nk), когда как авторский за O(k). Ну или за O(k log k), если надо отсортировать.