1

unsignedintのリストがあるとします。いくつかの要素が0に等しく、それらを押し戻したいとします。現在、私はこのコードを使用しています（listは、サイズnのunsignedintのリストへのポインターです。

for (i = 0; i < n; ++i) 
{    
    if (list[i])
        continue;
    int j;
    for (j = i + 1; j < n && !list[j]; ++j);
    int z;
    for (z = j + 1; z < n && list[z]; ++z);
    if (j == n)
        break;
    memmove(&(list[i]), &(list[j]), sizeof(unsigned int) * (z - j)));
    int s = z - j + i;
    for(j = s; j < z; ++j) 
        list[j] = 0;
    i = s - 1;
}

このタスクを実行するためのより効率的な方法を考えられますか？

スニペットは純粋に理論的なものであり、製品コードでは、リストの各要素は64バイトの構造体です。

編集：私は私の解決策を投稿します。ジョナサン・レフラーに感謝します。

void RemoveDeadParticles(int * list, int * n)
{
    int i, j = *n - 1;
    for (; j >= 0 && list[j] == 0; --j);
    for (i = 0; i <= j; ++i)
    {   
        if (list[i])
            continue;
        memcpy(&(list[i]), &(list[j]), sizeof(int));
        list[j] = 0;
        for (; j >= 0 && list[j] == 0; --j);
        if (i == j)
            break;
    }   

    *n = i;
}
4

4 に答える 4

2

次のコードの方がいいと思います。また、ゼロ以外の要素の順序を保持します

int nextZero(int* list, int start, int n){
   int i = start;
   while(i < n && list[i])
        i++;
   return i;
}

int nextNonZero(int* list, int start, int n){
   int i = start;
   while(i < n && !list[i])
        i++;
   return i;
}

void pushbackzeros(int* list, int n){
    int i = 0;
    int j = 0;
    while(i < n && j < n){
         i = nextZero(list,i, n);
         j = nextNonZero(list,i, n);
         if(i >= n || j >=n)
             return;
         list[i] = list[j];
         list[j] = 0;
    }
}

アイデア：

  • 最初のゼロ位置を見つけます（i）
  • 次のゼロ以外の位置を見つけます（j）
  • 順序が正しくない場合は交換します
  • 現在の位置から再開します（またはスワップ用の新しいゼロ以外の要素を見つけます）

複雑さ：O(n)。最悪の場合、各インデックスは最大4回（1回は、関数内iで1回j）、次にスワップ中にアクセスされます。

編集：前のコードは壊れていました。これはまだO(n)モジュール式です。

編集：

上記のコードの複雑さはO（n ^ 2）です。これは、インデックスjが「戻って」ゼロ以外のアイテムを探す、つまり、すでに持っているアイテムを調べることができるためです。次のゼロが次の非ゼロの前にあるときに発生します。修正はかなり簡単です、

  j = nextNonZero(list,MAX(i,j), n);

それよりも

  j = nextNonZero(list,i, n);
于 2012-09-20T15:31:12.480 に答える
2

以下のコードは、コメントで概説した線形アルゴリズムを実装しています。

注意すれば、直線的な線形O（N）アルゴリズムがあります。あなたのものはO（N 2）です。その順序は無関係であるため、配列内でゼロに遭遇するたびに、ゼロではない可能性のある最後の要素とそれを交換します。これは、アレイを1回通過することです。境界条件には注意が必要です。

注意が必要でした。テストコードのの酸テストはlist3[]、境界条件が正しくなるまで悲しみを引き起こしました。サイズ0または1のリストはすでに正しい順序になっていることに注意してください。

#include <stdio.h>
#define DIM(x)  (sizeof(x)/sizeof(*(x)))

extern void shunt_zeroes(int *list, size_t n);

void shunt_zeroes(int *list, size_t n)
{
    if (n > 1)
    {
        size_t tail = n;
        for (size_t i = 0; i < tail - 1; i++)
        {
            if (list[i] == 0)
            {
                while (--tail > i + 1 && list[tail] == 0)
                    ;
                if (tail > i)
                {
                    int t = list[i];
                    list[i] = list[tail];
                    list[tail] = t;
                }
            }
        }
    }
}

static void dump_list(const char *tag, int *list, size_t n)
{
    printf("%-8s", tag);
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", list[i]);
    }
    putchar('\n');
    fflush(0);
}

static void test_list(int *list, size_t n)
{
    dump_list("Before:", list, n);
    shunt_zeroes(list, n);
    dump_list("After:", list, n);
}

int main(void)
{
    int list1[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5 };
    int list2[] = { 1, 2, 2, 0, 3, 0, 4, 0, 0 };
    int list3[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int list4[] = { 0, 1 };
    int list5[] = { 0, 0 };
    int list6[] = { 0 };
    test_list(list1, DIM(list1));
    test_list(list2, DIM(list2));
    test_list(list3, DIM(list3));
    test_list(list4, DIM(list4));
    test_list(list5, DIM(list5));
    test_list(list6, DIM(list6));
}

実行例：

$ shuntzeroes
Before: 1 0 2 0 3 0 4 0 5 
After:  1 5 2 4 3 0 0 0 0 
Before: 1 2 2 0 3 0 4 0 0 
After:  1 2 2 4 3 0 0 0 0 
Before: 0 0 0 0 0 0 0 0 0 
After:  0 0 0 0 0 0 0 0 0 
Before: 0 1 
After:  1 0 
Before: 0 0 
After:  0 0 
Before: 0 
After:  0 
$

コードの複雑さ

質問とUmNyobeによる回答の元のコードはO（N 2）ですが、これはO（N）であると断言しました。ただし、3つのケースすべてでループ内にループがあります。他がO（N 2）であるのに、なぜこの答えは線形なのですか？

良い質問！

違いは、コードの内側のループが配列を逆方向にスキャンし、ゼロ以外の値を見つけて、見つかったばかりのゼロと交換することです。そうすることで、それは外側のループによって行われるべき仕事を減らします。したがって、2つが中央で出会うまで、インデックスiは1回前方にスキャンし、インデックスは1回後方にスキャンします。tail対照的に、元のコードでは、内部ループは現在のインデックスから始まり、毎回最後まで進みます。これにより、2次動作が発生します。

複雑さのデモンストレーション

UmNyobeとArgemanの両方が、UmNyobeの回答のコードは線形（O（N））であり、回答へのコメントで主張したように2次（O（N 2 ））ではないと主張しています。2つの反対意見を踏まえて、アサーションをチェックするプログラムを作成しました。

これは、これを十分に実証するテストの結果です。によって記述されたコード"timer.h"は、私のプラットフォームニュートラルタイミングインターフェイスです。そのコードはリクエストに応じて利用可能にすることができます（私のプロファイルを参照）。テストは、2.3 GHz Intel Core i7、Mac OS X 10.7.5、GCC4.7.1を搭載したMacBookProで実行されました。

UmNyobeのコードに加えた唯一の変更は、配列インデックスをからに変更しintてsize_t、外部関数インターフェイスが私のものと同じになるようにし、内部整合性を保つことでした。

テストコードには、関数が同等の答えを生成することを示すウォームアップ演習が含まれています。UmNyobeの答えは配列の順序を保持しますが、私の答えは保持しません。タイミングデータからその情報を省略しました。

$ make on2
gcc -O3 -g -I/Users/jleffler/inc -std=c99 -Wall -Wextra -L/Users/jleffler/lib/64 on2.c -ljl -o on2
$

タイミング

セット1：UmNyobeの修正されたアルゴリズムのない古いバージョンのテストハーネス。

shunt_zeroes:        100    0.000001
shunt_zeroes:       1000    0.000005
shunt_zeroes:      10000    0.000020
shunt_zeroes:     100000    0.000181
shunt_zeroes:    1000000    0.001468
pushbackzeros:       100    0.000001
pushbackzeros:      1000    0.000086
pushbackzeros:     10000    0.007003
pushbackzeros:    100000    0.624870
pushbackzeros:   1000000   46.928721
shunt_zeroes:        100    0.000000
shunt_zeroes:       1000    0.000002
shunt_zeroes:      10000    0.000011
shunt_zeroes:     100000    0.000113
shunt_zeroes:    1000000    0.000923
pushbackzeros:       100    0.000001
pushbackzeros:      1000    0.000097
pushbackzeros:     10000    0.007077
pushbackzeros:    100000    0.628327
pushbackzeros:   1000000   41.512151

マシンにはせいぜい非常に軽いバックグラウンド負荷がありました。たとえば、通常バックグラウンドで実行しているBoinc計算を一時停止しました。詳細なタイミングは思ったほど安定していませんが、結論は明らかです。

  • 私のアルゴリズムはO（N）です
  • UmNyobeの（元の）アルゴリズムはO（N 2）です。

セット2：UmNyobeの修正されたアルゴリズムを使用

Patrikの前後のアルゴリズムとWildplasserのアルゴリズムも含まれます（以下のソースを参照）。テストプログラムの名前がからon2に変更されましたtimezeromoves。

$ ./timezeromoves -c -m 100000 -n 1
shunt_zeroes: (Jonathan)
shunt_zeroes:        100    0.000001
shunt_zeroes:       1000    0.000003
shunt_zeroes:      10000    0.000018
shunt_zeroes:     100000    0.000155
RemoveDead: (Patrik)
RemoveDead:          100    0.000001
RemoveDead:         1000    0.000004
RemoveDead:        10000    0.000018
RemoveDead:       100000    0.000159
pushbackzeros2: (UmNyobe)
pushbackzeros2:      100    0.000001
pushbackzeros2:     1000    0.000005
pushbackzeros2:    10000    0.000031
pushbackzeros2:   100000    0.000449
list_compact: (Wildplasser)
list_compact:        100    0.000004
list_compact:       1000    0.000005
list_compact:      10000    0.000036
list_compact:     100000    0.000385
shufflezeroes: (Patrik)
shufflezeroes:       100    0.000003
shufflezeroes:      1000    0.000069
shufflezeroes:     10000    0.006685
shufflezeroes:    100000    0.504551
pushbackzeros: (UmNyobe)
pushbackzeros:       100    0.000003
pushbackzeros:      1000    0.000126
pushbackzeros:     10000    0.011719
pushbackzeros:    100000    0.480458
$

これは、他のソリューションと同様に、UmNyobeの修正されたアルゴリズムがO（N）であることを示しています。UmNyobeの元のアルゴリズムと同様に、元のコードはO（N 2 ）であることが示されています。

ソース

これは修正されたテストプログラムです（に名前が変更されましたtestzeromoves.c）。アルゴリズムの実装は一番上にあります。テストハーネスは、コメント「テストハーネス」の後にあります。コマンドは、チェックまたはタイミング、あるいはその両方を実行できます（デフォルト）。デフォルトでは2回の反復を行います。デフォルトでは、最大100万エントリのサイズになります。フラグを使用して-cチェックを省略し、フラグを使用して-tタイミングを省略し、フラグを使用して-n反復回数を-m指定し、フラグを使用して最大サイズを指定できます。100万を超えることには注意してください。おそらく、スタックを爆破するVLA（可変長配列）で問題が発生するでしょう。代わりmalloc()に使用するコードを変更するのは簡単です。free()しかし、それは必要ではないようです。

#include <string.h>

#define MAX(x, y)   (((x) > (y)) ? (x) : (y))

extern void shunt_zeroes(int *list, size_t n);
extern void pushbackzeros(int *list, size_t n);
extern void pushbackzeros2(int *list, size_t n);
extern void shufflezeroes(int *list, size_t n);
extern void RemoveDead(int *list, size_t n);
extern void list_compact(int *arr, size_t cnt);

void list_compact(int *arr, size_t cnt)
{
    size_t dst,src,pos;

    /* Skip leading filled area; find start of blanks */
    for (pos=0; pos < cnt; pos++) {
        if ( !arr[pos] ) break;
    }
    if (pos == cnt) return;

    for(dst= pos; ++pos < cnt; ) { 
        /* Skip blanks; find start of filled area */
        if ( !arr[pos] ) continue;

        /* Find end of filled area */
        for(src = pos; ++pos < cnt; ) {
            if ( !arr[pos] ) break;
        }   
        if (pos > src) {
            memmove(arr+dst, arr+src, (pos-src) * sizeof arr[0] );
            dst += pos-src;
        }   
    }
}

/* Cannot change j to size_t safely; algorithm relies on it going negative */
void RemoveDead(int *list, size_t n)
{
    int i, j = n - 1;
    for (; j >= 0 && list[j] == 0; --j)
        ;
    for (i = 0; i <= j; ++i)
    {   
        if (list[i])
            continue;
        memcpy(&(list[i]), &(list[j]), sizeof(int));
        list[j] = 0;
        for (; j >= 0 && list[j] == 0; --j);
        if (i == j)
            break;
    }   
}

void shufflezeroes(int *list, size_t n)
{
    for (size_t i = 0; i < n; ++i) 
    {    
        if (list[i])
            continue;
        size_t j;
        for (j = i + 1; j < n && !list[j]; ++j)
            ;
        size_t z;
        for (z = j + 1; z < n && list[z]; ++z)
            ;
        if (j == n)
            break;
        memmove(&(list[i]), &(list[j]), sizeof(int) * (z - j));
        size_t s = z - j + i;
        for(j = s; j < z; ++j) 
            list[j] = 0;
        i = s - 1;
    } 
}

static int nextZero(int* list, size_t start, size_t n){
   size_t i = start;
   while(i < n && list[i])
        i++;
   return i;
}

static int nextNonZero(int* list, size_t start, size_t n){
   size_t i = start;
   while(i < n && !list[i])
        i++;
   return i;
}

void pushbackzeros(int* list, size_t n){
    size_t i = 0;
    size_t j = 0;
    while(i < n && j < n){
         i = nextZero(list,i, n);
         j = nextNonZero(list,i, n);
         if(i >= n || j >=n)
             return;
         list[i] = list[j];
         list[j] = 0;
    }
}

/* Amended algorithm */
void pushbackzeros2(int* list, size_t n){
    size_t i = 0;
    size_t j = 0;
    while(i < n && j < n){
         i = nextZero(list, i, n);
         j = nextNonZero(list, MAX(i,j), n);
         if(i >= n || j >=n)
             return;
         list[i] = list[j];
         list[j] = 0;
    }
}

void shunt_zeroes(int *list, size_t n)
{
    if (n > 1)
    {
        size_t tail = n;
        for (size_t i = 0; i < tail - 1; i++)
        {
            if (list[i] == 0)
            {
                while (--tail > i + 1 && list[tail] == 0)
                    ;
                if (tail > i)
                {
                    int t = list[i];
                    list[i] = list[tail];
                    list[tail] = t;
                }
            }
        }
    }
}

/* Test Harness */

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "timer.h"

#define DIM(x)      (sizeof(x)/sizeof(*(x)))

typedef void (*Shunter)(int *list, size_t n);

typedef struct FUT      /* FUT = Function Under Test */
{
    Shunter function;
    const char *name;
    const char *author;
} FUT;

static int tflag = 1;   /* timing */
static int cflag = 1;   /* checking */
static size_t maxsize = 1000000;

static void dump_list(const char *tag, int *list, size_t n)
{
    printf("%-8s", tag);
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", list[i]);
    }
    putchar('\n');
    fflush(0);
}

static void test_list(int *list, size_t n, Shunter s)
{
    dump_list("Before:", list, n);
    (*s)(list, n);
    dump_list("After:", list, n);
}

static void list_of_tests(const FUT *f)
{
    int list1[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5 };
    int list2[] = { 1, 2, 2, 0, 3, 0, 4, 0, 0 };
    int list3[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int list4[] = { 0, 1 };
    int list5[] = { 0, 0 };
    int list6[] = { 0 };

    test_list(list1, DIM(list1), f->function);
    test_list(list2, DIM(list2), f->function);
    test_list(list3, DIM(list3), f->function);
    test_list(list4, DIM(list4), f->function);
    test_list(list5, DIM(list5), f->function);
    test_list(list6, DIM(list6), f->function);
}

static void test_timer(int *list, size_t n, const FUT *f)
{
    Clock t;
    clk_init(&t);
    clk_start(&t);
    f->function(list, n);
    clk_stop(&t);
    char buffer[32];
    printf("%-15s  %7zu  %10s\n", f->name, n, clk_elapsed_us(&t, buffer, sizeof(buffer)));
    fflush(0);
}

static void gen_test(size_t n, const FUT *f)
{
    int list[n];
    for (size_t i = 0; i < n/2; i += 2)
    {
        list[2*i+0] = i;
        list[2*i+1] = 0;
    }   
    test_timer(list, n, f);
}

static void timed_run(const FUT *f)
{
    printf("%s (%s)\n", f->name, f->author);
    if (cflag)
        list_of_tests(f);
    if (tflag)
    {
        for (size_t n = 100; n <= maxsize; n *= 10)
            gen_test(n, f);
    }
}

static const char optstr[] = "cm:n:t";
static const char usestr[] = "[-ct][-m maxsize][-n iterations]";

int main(int argc, char **argv)
{
    FUT functions[] =
    {
        { shunt_zeroes,   "shunt_zeroes:",   "Jonathan"    },   /* O(N) */
        { RemoveDead,     "RemoveDead:",     "Patrik"      },   /* O(N) */
        { pushbackzeros2, "pushbackzeros2:", "UmNyobe"     },   /* O(N) */
        { list_compact,   "list_compact:",   "Wildplasser" },   /* O(N) */
        { shufflezeroes,  "shufflezeroes:",  "Patrik"      },   /* O(N^2) */
        { pushbackzeros,  "pushbackzeros:",  "UmNyobe"     },   /* O(N^2) */
    };
    enum { NUM_FUNCTIONS = sizeof(functions)/sizeof(functions[0]) };
    int opt;
    int itercount = 2;

    while ((opt = getopt(argc, argv, optstr)) != -1)
    {
        switch (opt)
        {
        case 'c':
            cflag = 0;
            break;
        case 't':
            tflag = 0;
            break;
        case 'n':
            itercount = atoi(optarg);
            break;
        case 'm':
            maxsize = strtoull(optarg, 0, 0);
            break;
        default:
            fprintf(stderr, "Usage: %s %s\n", argv[0], usestr);
            return(EXIT_FAILURE);
        }
    }

    for (int i = 0; i < itercount; i++)
    {
        for (int j = 0; j < NUM_FUNCTIONS; j++)
            timed_run(&functions[j]);
        if (tflag == 0)
            break;
        cflag = 0;  /* Don't check on subsequent iterations */
    }

    return 0;
}
于 2012-09-20T16:46:49.450 に答える
1

これが私の試みです。戻り値は、配列に存在するメンバーの数です（それ以降は無視する必要があります!!）：

#include <stdio.h>
#include <string.h>

size_t list_compact(int *arr, size_t cnt);

size_t list_compact(int *arr, size_t cnt)
{
    size_t dst,src,pos;

    /* Skip leading filled area; find start of blanks */
    for (pos=0; pos < cnt; pos++) {
        if ( !arr[pos] ) break;
        }
    if (pos == cnt) return pos;

    for(dst= pos; ++pos < cnt; ) { 
        /* Skip blanks; find start of filled area */
        if ( !arr[pos] ) continue;

        /* Find end of filled area */
        for(src = pos; ++pos < cnt; ) {
            if ( !arr[pos] ) break;
            }   
        if (pos > src) {
            memcpy(arr+dst, arr+src, (pos-src) * sizeof arr[0] );
            dst += pos-src;
            }   
        }
#if MAINTAIN_ORIGINAL_API || JONATHAN_LEFFLFER
     if (cnt > src) memset( arr + src, 0, (cnt-src) * sizeof arr[0] );
#endif
    return dst;
}

更新：これは、ジョナサンレフラーシャッフルメソッドのコンパクトバージョンです（元の順序を維持しません）：

size_t list_compact(int *arr, size_t cnt)
{
    int *beg,*end;
    if (!cnt) return 0;

    for (beg = arr, end=arr+cnt-1; beg <= end; ) {
        if ( *beg ) { beg++; continue; }
        if ( !*end ) { end--; continue; }
        *beg++ = *end--;
        }

#if WANT_ZERO_THE_TAIL
        if (beg < arr+cnt) memset(beg, 0, (arr+cnt-beg) *sizeof *arr);
        return cnt;
#else
    return beg - arr;
#endif
}

更新:(JonathanLefflerに感謝）バッファがオーバーラップすることは不可能であるため、memmove（）は実際にはmemcpy（）である必要があります。

GCC 4.6.1では、memcpy（）をインライン化するために-minline-all-stringopsが必要です。memmove（）はインライン化されないので、そう思われます。

インライン化は、実際に移動される量に比べて関数呼び出しのオーバーヘッドが非常に大きいため、パフォーマンスが向上します（のみsizeof(int)）

于 2012-09-20T22:20:05.823 に答える
0

ばかばかしいほど単純なO（n）アルゴリズムは、リストをトラバースすることです。ゼロエントリに遭遇するたびにリストを削除し、このプロセス中に削除したエントリの数Mを記録し、リストのトラバースが終了したら、その数を追加するだけです。リストの最後にあるゼロエントリのM。

これには、連続する要素をN回チェックする必要があります。ここで、Nはリストの長さ、Mは削除、Mはリストの最後に挿入します。最悪のシナリオでは、リスト全体がゼロエントリで満たされている場合、N回の読み取り、N回の削除、およびN回の挿入を実行します。

于 2012-09-20T19:17:14.833 に答える