2

私は2つのリストを持っています。

char *name[] =  {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"};
char *name_to_remove[] =  {"RGS", "O", "NRGY"};

アイテムのリストを取得して別のリストから削除する効果的な方法はありますか？私は自分のバージョンを実装しましたが、それはかなり非効率的だと思います。基本的に、名前リストのコピーを作成し、ネストされたforループを使用して、複製された名前リストとname_to_removeリストの両方を調べ、「削除」を繰り返すアイテムにマークを付けます。最後に、リストを調べて、値が「remove」のアイテムを除くすべてのアイテムをコピーします。そのひどく醜く、私は非効率的だと思います。私が問題を抱えている（以前に対処したことがない）問題は、配列がメモリ内の固定サイズである場合に配列からアイテムを削除できるかどうかわからないため、最初に変更しようとしました値を入力してから、値を新しい配列に追加します（元の配列と同じサイズ-削除するアイテムの配列のサイズ）。

私はそれを行うためのより良い方法を見つけることができません。memcmpは2つのリストを比較できるので有望であるように見えましたが、それがどのように適合するかを理解できませんでした。私はCがPythonではないことを知っていますが、Pythonでそれをきれいに行う方法は次のとおりです。

for item in name_to_remove:
    name_copy.remove(item)

おそらくシーンの下で、pythonコマンドは私がしているのと同じくらい多くのループを行っていますが、私は尋ねると思いました。

4

6 に答える 6

2

これに対する答えは、適切なデータ構造を使用することです。Pythonリストは文字列のプレーンC配列として実装されていないことは間違いありません（Pythonリストにさまざまなタイプのオブジェクトを格納できるからです）。したがって、探しているデータ構造は、おそらくリンクリストまたはハッシュテーブルのいずれかです。

于 2012-06-03T02:39:57.260 に答える
1

基本的に、名前リストのコピーを作成し、ネストされたforループを使用して、複製された名前リストとname_to_removeリストの両方を調べ、「削除」を繰り返すアイテムにマークを付けます。最後に、リストを調べて、値が「remove」のアイテムを除くすべてのアイテムをコピーします。

何かにマークを付ける代わりに、そこにないアイテムをコピーして新しい配列に格納し、古い配列をゴミ箱に移動するnameことができます。name_to_removename

于 2012-06-03T02:40:59.170 に答える
1

文字列の順序が重要でない場合は、次のように両方の配列を並べ替えて重複を見つけることができます。

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

#define ARR_SIZE(array) sizeof(array)/sizeof(const char *)

int compare (const void * a, const void * b) {
    return strcmp(*((const char**)a), *((const char**)b));
}

int main(void) {
    const char *name[] =  {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"};
    const char *name_to_remove[] =  {"RGS", "O", "NRGY"};
    int i = 0, j = 0;
    qsort(name, ARR_SIZE(name), sizeof(const char*), compare);
    qsort(name_to_remove, ARR_SIZE(name_to_remove), sizeof(const char*), compare);
    while (i != ARR_SIZE(name) && j != ARR_SIZE(name_to_remove)) {
            int diff = strcmp(name[i], name_to_remove[j]);
            if (diff == 0) {
                    name[i] = NULL;
                    i++;
                    j++;
            } else if (diff < 0) {
                    i++;
            } else {
                    j++;
            }
    }
    for (i = 0 ; i != ARR_SIZE(name) ; i++)
            if (name[i])
                    printf("%s\n", name[i]);
    return 0;
}
于 2012-06-03T03:19:39.510 に答える
0

ハッシュマップを作成し、1つの配列をループしてテストしmapOfRemovableWords.contains(words[i])、それを使用して要素を新しい配列（またはそれ自体の前面）にコピーする必要があるかどうかを判断できます。

両方の配列を並べ替えて、同時にそれらを反復処理することもできます。ある単語が他のリストの現在の単語よりも大きい位置にいる場合は、他のリストにはないという事実を使用してください。一方を繰り返してから、もう一方を繰り返す必要があるかどうかを判断し、両方を完全に移動するまで繰り返します。

于 2012-06-03T02:40:51.253 に答える
0

Pythonバージョンはあなたのコードよりもはるかに効率的ではないと思います。

そうは言っても、実装を確実に改善することができます。C配列は、実際には文字列の先頭へのポインタの束を備えた単なるメモリブロックであることを忘れないでください。新しい文字列を作成していないので、いつでも文字列ポインタを再利用できます。

概念的には、配列をループし、削除する値がリストにある場合はポインターをnullに設定します。次に、malloc（）を使用して、適切なサイズの新しい配列を作成します。古い配列をループし、null以外のポインターを新しい配列にコピーします。

このようにして、2つのループ反復と1つのmallocが得られます。

于 2012-06-03T02:40:57.113 に答える
0

コンパイル時に最初の配列を割り当てると、そのサイズは固定され、選択した要素を「削除」することによって、後でメモリを再利用することはできないと思います。動的に割り当てることができるリンクリストを実装し、その後free()、アイテムを削除したいときはいつでもその一部を実装するか、さらに良いことに、バイナリ検索ツリーなどのより効率的なデータ構造を実装することをお勧めします。

于 2012-06-03T02:44:17.743 に答える