2

В статье Stable Minimum Storage Merging by Symmetric Comparisons приведен псевдокод алгоритма, по которому я написал программу на С (код здесь).

Она не работает (результат слияния 2-х упорядоченных массивов не упорядочен).

Собственно, вопросы:

  1. Я ошибся в перекодировании алгоритма с псевдокода на C ?
  2. или я чего-то не понял в статье и приведенный алгоритм в принципе не работает ? (с чего бы это ?)

Алгоритм

Algorithm 1 Symmerge algorithm

Symmerge (A, first1, first2, last)
  if first1 < first2 and first2 < last then
    m <-  (first1 + last)/2
    n <-  m + first2
    if first2 > m then
      start <-  Bsearch (A, n - last, m, n - 1)
    else
      start <-  Bsearch (A, first1, first2, n - 1)
    end <-  n - start
    Rotate (A, start, first2, end)
    Symmerge (A, first1, start, m)
    Symmerge (A, m, end, last)

Bsearch (A, l, r, p)
  while l < r
    m <-  (l + r ) / 2
    if A[m] <= A[p - m]
      then l   m + 1 ;
      else r   m;
  return l

Часть кода, соответствующая алгоритму

Symmerge (int A[], int first1, int first2, int last)
{
  printf ("Symm %d %d %d\n",first1,first2,last);
  int start, end, m, n;

  if (first1 < first2 && first2 < last) {
    m = (first1 + last)/2;
    n =  m + first2;
    if (first2 > m) {
      start =  Bsearch (A, n - last, m, n - 1);
    } else { 
      start =  Bsearch (A, first1, first2, n - 1);
    }
    end = n - start;

    Rotate (A, start, first2, end);
    Symmerge (A, first1, start, m);
    Symmerge (A, m, end, last);
  }
}

int
Bsearch (int A[], int l, int r, int p)
{
  int m;
  while (l < r) {
    m = (l + r ) / 2;
    if (A[m] <= A[p - m])
      l =   m + 1 ;
    else r = m;
  }
  return l;
}

Функцию Rotate() тестировал (да и в ее коде печать массива до и после есть), крутит нормально.

Вожусь давно, почему не работает (точнее почему этот алгоритм должен работать) не понимаю.

В тайне надеюсь, что я что-то не понял в псевдокоде и поэтому не работает.

UPDATE 1 (на комментарий @jmu)

Rotate

Взято отсюда

Псевдокод

/* Функция swap(a, b, m) меняем местами:
 * x[a..a+m-1] и x[b..b+m-1]
 */

if rotdist == 0 || rotdist == n
  exit

i = p = rotdist
j = n - p
while i != j
  /* инвариант:
     x[0..p-i] двигать не нужно
     x[p-i..p-1] = a (нужно поменять с b)
     x[p..p+j-1] = b (нужно поменять с a)
     x[p+j..n-1] двигать не нужно */

  if i > j
    swap(p-i, p, j)
    i -= j
  else
    swap(p-i, p+j-i, i)
    j -= i
swap(p-i, p, i)

Реализация Rotate

void
swap (int a[], int f, int t, int l)
{
  int tt;

  for (l+=f; f < l; f++,t++) {
    tt = a[f];
    a[f] = a[t];
    a[t] = tt;
  }
}

void
rotate (int a[], int n, int dist)
{
  if (dist == 0 || dist == n)
    return;
  int i, j, p;
  i = p = dist;
  j = n - p;
  while (i != j) {
    if (i > j) {
      swap (a, p-i,p,j);
      i -= j;
    } else {
      swap (a, p-i,p+j-i,i);
      j -= i;
    }
  }
  swap (a, p-i,p,i);
}

Rotate (int *A, int left, int r, int end)
{
  int *a = A+left, n = end-left+1, m = r-left;
  printf ("l=%d r=%d e=%d\n",left,r,end);
  pri("++ ");
  rotate (a,n,m);
  pri("-- ");
}
6
  • интересно, завтра на работе попробую закодить. добавте пожалуйста еще псевдокод rotate :)
    – jmu
    13 фев 2012 в 23:08
  • update1: у меня после выполнения первой ротации результат уже не совпадает с тем что у авторов используется в качестве примера
    – jmu
    14 фев 2012 в 16:10
  • Странно, у меня в начальной последовательности 0 2 5 9 1 4 7 8 сначала, как и у авторов меняются местами [5 9] с [1 4] 0 2 1 4 5 9 7 8 затем в левой части 2 с 1 и потом вызывается Rotate() для обмена 2 с самим собой. В общем левая часть упорядочивается 0 1 2 4 5 9 7 8 а затем фигня. Упорядочивание правой части начинается не с [5 9][7 8], а с [4 5][9 7 8]. -- Вот этот момент в псевокоде я совсем не понимаю Symmerge (A, first1, start, m) Symmerge (A, m, end, last)
    – avp
    14 фев 2012 в 19:11
  • Совершенно перестал редактироваться комментарий, все уходит за границу окна (наверное слишком длинный). -- Так вот, одно и то же m в первом и втором вызовах не понимаю. Не понимаю и еще кое-какие моменты (например, один и то же end в Rotate() и втором Symmerge()). IMHO это противоречит алгоритму, описываемому в статье словами. Или я чего-то не понимаю в псевдокоде (например, что "очевидные" изменения переменных в нем опускаются) ?
    – avp
    14 фев 2012 в 19:24
  • есть несколько вопросов насчет метода rotate: 1) сдвиг вправо/влево? 2) аргументы метода: 1 - массив , 2 - index первого элемента, 3 - количество ротаций, 4 - index последнего элемента ?
    – jmu
    15 фев 2012 в 11:29

1 ответ 1

3

заработало, вы уж простите код на java:

import java.util.Arrays ;

public class TestMerge
{
    public static void main ( String[] args )
    {
        // define two sorted arrays
        int[] m = new int[] { 0, 2, 5, 9 } ;
        int[] n = new int[] { 1, 4, 7, 8 } ;

        // concat arrays
        int[] both = new int[m.length + n.length] ;
        for ( int i = 0 ; i < m.length ; i++ )
        {
            both[i] = m[i] ;
        }
        for ( int i = 0 ; i < n.length ; i++ )
        {
            both[m.length + i] = n[i] ;
        }

        dump ( both ) ;

        symmerge ( both, 0, m.length, both.length ) ;
    }

    private static void dump ( int[] both )
    {
        System.out.println ( Arrays.toString ( both ) ) ;
    }

    public static void symmerge ( int[] a, int first1, int first2, int last )
    {
        if ( first1 < first2 && first2 < last )
        {
            // m, n
            int m = (first1 + last) / 2 ;
            int n = m + first2 ;

            // start, end
            int start ;
            if ( first2 > m )
            {
                start = bsearch ( a, n - last, m, n - 1 ) ;
            }
            else
            {
                start = bsearch ( a, first1, first2, n - 1 ) ;
            }
            int end = n - start ;

            rotate ( a, start, first2, end - 1 ) ;

            symmerge ( a, first1, start, m ) ;
            symmerge ( a, m, end, last ) ;
        }
    }

    public static int bsearch ( int[] a, int l, int r, int p )
    {
        while ( l < r )
        {
            int m = (l + r) / 2 ;
            if ( a[m] <= a[p - m] )
            {
                l = m + 1 ;
            }
            else
            {
                r = m ;
            }
        }
        return l ;
    }

    public static void rotate ( int[] a, int first, int second, int end )
    {
        if ( first != second )
        {
            int rotation = first - second ;
            if ( rotation < 0 )
            {
                rotation = rotation + (end - first + 1) ;
            }

            // rotate
            rotateImpl ( a, first, end, rotation ) ;
        }
    }

    private static void rotateImpl ( int[] a, int start, int end, int rotation )
    {
        int tmp ;
        for ( int i = 0 ; i < rotation ; i++ )
        {
            tmp = a[end] ;
            for ( int j = end ; j > start ; j-- )
            {
                a[j] = a[j - 1] ;
            }
            a[start] = tmp ;
        }

        dump ( a ) ;
    }
}

результат (новая строчка после каждого rotate):

[0, 2, 5, 9, 1, 4, 7, 8]
[0, 2, 1, 4, 5, 9, 7, 8]
[0, 1, 2, 4, 5, 9, 7, 8]
[0, 1, 2, 4, 5, 7, 9, 8]
[0, 1, 2, 4, 5, 7, 8, 9]

p.s не стоит забывать что надо соблюдать условие для длинны массивов m >=n

тест с другим набором входных данных:

    int[] m = new int[] { 0, 2, 5, 9, 11, 13, 15 } ;
    int[] n = new int[] { 1, 4, 7, 8, 9, 11 } ;

результат:

[0, 2, 5, 9, 11, 13, 15, 1, 4, 7, 8, 9, 11]
[0, 2, 5, 1, 4, 7, 9, 11, 13, 15, 8, 9, 11]
[0, 2, 1, 5, 4, 7, 9, 11, 13, 15, 8, 9, 11]
[0, 2, 1, 5, 4, 7, 9, 11, 13, 15, 8, 9, 11]
[0, 1, 2, 5, 4, 7, 9, 11, 13, 15, 8, 9, 11]
[0, 1, 2, 4, 5, 7, 9, 11, 13, 15, 8, 9, 11]
[0, 1, 2, 4, 5, 7, 9, 8, 9, 11, 13, 15, 11]
[0, 1, 2, 4, 5, 7, 8, 9, 9, 11, 13, 15, 11]
[0, 1, 2, 4, 5, 7, 8, 9, 9, 11, 11, 13, 15]
4
  • ошибка в вызове метода rotate, еще раз извините за java код, разницу в синтаксисе пытался свести к минимуму
    – jmu
    15 фев 2012 в 16:31
  • Спасибо, попробую разобраться. Если не сложно, словами, в чем суть ошибки ? Ага, увидел. Все таки last это не индекс последнего, а длина 2-х последовательностей (индекс следующего за последним). Значит и end в Rotate() имеет тот же смысл. Еще раз спасибо, в ближайшее время попробую на C.
    – avp
    15 фев 2012 в 19:48
  • Ну для увеличения скорости можно в rotate определять, в какую сторону крутить меньше.
    – alexlz
    16 фев 2012 в 0:08
  • Все работает на С. Действительно сортировка с этим слиянием работает шустро, на массиве из 1000000 элементов всего в 3 раза медленнее, чем у аналогичной tim_sort (которой требуется дополнительная память). Время работы tim_sort N * log N, а с слиянием без доп. памяти N * (log N)^2. Для массива из 10000000 отставание возросло всего до 3.7 раза (!) Для 100000 время отличается всего в 1.5 раза (!!!).
    – avp
    16 фев 2012 в 7:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.