1

私は次の問題で立ち往生しています：

int sort_compare(const void *x, const void *y) {
    const int *xi = *(const int **) x;
    const int *yi = *(const int **) y;

    for (int i = 0; i < block_size; i++) {
        comp_x[i] = block[(*xi + i) % block_size];
        comp_y[i] = block[(*yi + i) % block_size];
    }

    return memcmp(comp_x, comp_y, block_size);
}

void sort() {
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
    qsort(to_sort, block_size, sizeof (int), sort_compare);
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
}

values:
    block_size = 5;
    block = "jkldj";
    comp_x, compy_y and to_sort are well allocated

output:
    0,1,2,3,4,
    3,0,1785357420,1,1684826986,

to_sort には、(循環) 文字列の最初の文字が含まれます。

qwer
werq
erqw
rqwe

、(0,1,2,3) として表されるものは、次のように並べ替える必要があります

erqw
rqwe
qwer
werq

、(2,3,0,1) として表されます。数値が非常に大きいように見えますが、それはなぜですか?

前もって感謝します！

4

3 に答える 3

2

xコンパレータにy渡される と は、配列要素へのポインタです。配列要素はints であるため、値を取得するには、ポインターをポインターにキャストして逆参照intする必要があります。コードに追加の間接レイヤーがあり、実際には次のようになります。voidint

int xi = *(const int *) x;
int yi = *(const int *) y;

次に、データ比較を行うときにandの代わりに and を直接xi使用します。yi*xi*yi

最適化として、データを別々の配列にコピーしてからmemcmpそれらをコピーする必要はありません。ループ内でそれらを自分で比較するだけです。

for (int i = 0; i < block_size; i++) {
    char data_x = block[(xi + i) % block_size];
    char data_y = block[(yi + i) % block_size];
    if (data_x != data_y)
        return data_x - data_y;
}

return 0;

さらに最適化するために、block配列内のデータを 2 倍にすると (たとえば"qwerqwer"、 だけではなく)、ラップアラウンドを処理する必要がなくなるため、 を "qwer"1 回呼び出すだけで比較を行うことができます。は高度に最適化されているため、大量のデータがある場合は、手書きの for ループよりもはるかに高速に使用できます。memcmpmemcmpmemcmp

于 2012-10-19T19:13:56.577 に答える
1

初期化するとき

const int *xi = *(const int **) x;
const int *yi = *(const int **) y;

の要素のアドレスは、to_sortとして解釈され、const int**次に逆参照されてとの値が与えられxiますyi。to_sortこれは、の値（int*sがsより大きい場合はそれを超える可能性がありintます）をポインターとして解釈します。

sをキャストする必要がありますvoid*：

const int *xi = (const int *) x;
const int *yi = (const int *) y;
于 2012-10-19T18:58:41.467 に答える
1

qsort() は、N 個のアイテムの線形リストを指定することで歌います。ここで、任意のアイテム (n) アドレスは、各「アイテム」のベース アドレス + サイズを使用して計算できます。簡単なものから始めましょう。簡単とは、ポインターのリストを意味します。

まず、バッファの循環性は、コピーを元のバッファに接合するだけでエミュレートできます (理想的には 1 文字未満ですが、1 バイトについては言いません)。いえ

"qwer" ==> "qwerqwer"

これは次の方法で実行できます。

char *buff = malloc(2 * blocksize);
memcpy(buff, to_sort, blocksize);
memcpy(buff+blocksize, to_sort, blocksize);

これで、オフセット 0..(blocksize-1) が得られました。それぞれが char のブロックサイズであり、特別なポインター計算なしで相互に比較できます。

次に、実際にソートするためのポインターのリストを作成します。この場合は、

char** ptrs = malloc(sizeof(char*) * blocksize); 
for (i=0;i<blocksize;i++)
    ptrs[i] = buff+i;

次に、2つの「アイテム」を比較する機能。アドレスによって渡される項目は、文字列へのポインターです。繰り返しますが、左と右のように過去のアドレスは、2 つの char * が見つかった場合のメモリ位置です。アドレス自体はchar *ではありません:

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}

最後に、これをそのまま qsort() に送信します。

qsort(ptrs, blocksize, sizeof(char*), block_compare);

最終的な出力は、作成された循環バッファーへのポインターのブロックサイズ長のリストであり、それぞれがブロックサイズサイズのチャンクを参照しています。上記のすべての全文は次のとおりです。

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

size_t blocksize = 0;

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}


int main(int argc, char* argv[])
{
    char to_sort[] = "qwer";
    size_t i = 0;

    // set blockize
    blocksize = strlen(to_sort);

    char *buff = malloc(2 * blocksize);
    memcpy(buff, to_sort, blocksize);
    memcpy(buff+blocksize, to_sort, blocksize);

    char ** ptrs = malloc(blocksize * sizeof(char*));
    for (i=0;i<blocksize;++i)
        ptrs[i] = buff+i;

    // now send the pointer list to qsort()
    qsort(ptrs, blocksize, sizeof(*ptrs), block_compare);

    // ptrs is sorted. do with it what you will.
    for (i=0;i<blocksize;i++)
    {
        fwrite(ptrs[i], sizeof(char), blocksize, stdout);
        fwrite("\n", sizeof(char), 1, stdout);
    }
    fflush(stdout);

    free(ptrs);
    free(buff);

    return EXIT_SUCCESS;
}

「qwer」を使用すると、以下が生成されます。

erqw
qwer
rqwe
werq

「asubstantallylongerstringtest」を使用した別のサンプル

allylongerstringtestasubstanti
antiallylongerstringtestasubst
asubstantiallylongerstringtest
bstantiallylongerstringtestasu
erstringtestasubstantiallylong
estasubstantiallylongerstringt
gerstringtestasubstantiallylon
gtestasubstantiallylongerstrin
iallylongerstringtestasubstant
ingtestasubstantiallylongerstr
llylongerstringtestasubstantia
longerstringtestasubstantially
lylongerstringtestasubstantial
ngerstringtestasubstantiallylo
ngtestasubstantiallylongerstri
ntiallylongerstringtestasubsta
ongerstringtestasubstantiallyl
ringtestasubstantiallylongerst
rstringtestasubstantiallylonge
stantiallylongerstringtestasub
stasubstantiallylongerstringte
stringtestasubstantiallylonger
substantiallylongerstringtesta
tantiallylongerstringtestasubs
tasubstantiallylongerstringtes
testasubstantiallylongerstring
tiallylongerstringtestasubstan
tringtestasubstantiallylongers
ubstantiallylongerstringtestas
ylongerstringtestasubstantiall

男私はそれがあなたが探していたものであることを願っています. （うわー）。

于 2012-10-19T19:57:13.017 に答える