Zadanie

Napisz program w wybranym języku, który odczyta wiersze wejścia ze standardowego wejścia do EOF, a następnie zapisze je na standardowym wyjściu w ASCIIbetical, podobnie jak program sortwiersza poleceń. Krótki, niedoceniony przykład w Pythonie to:

import sys

for line in sorted(sys.stdin):
    print(line.rstrip('\n'))

Podstępna część

Podobnie jak w przypadku Wojny OS , Twoim celem jest udowodnienie, że twoja ulubiona platforma jest „lepsza”, poprzez celowe uruchomienie programu znacznie wolniej na konkurencyjnej platformie. Na potrzeby tego konkursu „platforma” składa się z dowolnej kombinacji:

• Edytor
  • Architektura (x86, Alpha, ARM, MIPS, PowerPC itp.)
  • Bitowość (64-bit vs. 32-bit vs. 16-bit)
  • Big-versus little-endian
• System operacyjny
  • Windows vs. Linux vs. Mac OS itp.
  • Różne wersje tego samego systemu operacyjnego
• Implementacja języka
  • Różni dostawcy kompilatorów / interpreterów (np. MSVC ++ vs. GCC)
  • Różne wersje tego samego kompilatora / interpretera

Chociaż możesz spełnić wymagania, pisząc kod:

#ifndef _WIN32
    Sleep(1000);
#endif

Takiej odpowiedzi nie należy oceniać pozytywnie. Celem jest subtelność. Najlepiej byłoby, gdyby kod wyglądał tak, jakby w ogóle nie był zależny od platformy. Jeśli nie mają żadnych #ifdefoświadczeń (lub warunków opartych na os.namelub System.Environment.OSVersionlub cokolwiek), powinny one mieć wiarygodne uzasadnienie (oparte na kłamstwie, oczywiście).

Uwzględnij w swojej odpowiedzi

• Kod
• Twoje „ulubione” i „nieprzychylne” platformy.
• Dane wejściowe do testowania programu.
• Czas działania na każdej platformie dla tych samych danych wejściowych.
• Opis, dlaczego program działa tak wolno na niekorzystnej platformie.

do

CleverSort

CleverSort to najnowocześniejszy (tj. Nadmiernie skonstruowany i nieoptymalny) dwustopniowy algorytm sortowania ciągów.

W kroku 1 rozpoczyna się od wstępnego sortowania linii wejściowych za pomocą sortowania radix i pierwszych dwóch bajtów każdej linii. Sortowanie Radix jest nieporównywalne i działa bardzo dobrze dla łańcuchów.

W kroku 2 używa sortowania wstawiania na wstępnie posortowanej liście ciągów. Ponieważ lista jest prawie posortowana po kroku 1, sortowanie wstawiania jest dość wydajne w przypadku tego zadania.

Kod

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

// Convert first two bytes of Nth line into integer

#define FIRSTSHORT(N) *((uint16_t *) input[N])

int main()
{
    char **input = 0, **output, *ptemp;
    int first_index[65536], i, j, lines = 0, occurrences[65536];
    size_t temp;

    // Read lines from STDIN

    while(1)
    {
        if(lines % 1000 == 0)
            input = realloc(input, 1000 * (lines / 1000 + 1) * sizeof(char*));

        if(getline(&input[lines], &temp, stdin) != -1)
            lines++;
        else
            break;
    }

    output = malloc(lines * sizeof(char*));

    // Radix sort

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i < lines; i++) occurrences[FIRSTSHORT(i)]++;

    first_index[0] = 0;

    for(i = 0; i < 65536 - 1; i++)
        first_index[i + 1] = first_index[i] + occurrences[i];

    memset(occurrences, 0, 65536 * sizeof(int));

    for(i = 0; i < lines; i++)
    {
        temp = FIRSTSHORT(i), output[first_index[temp] + occurrences[temp]++] = input[i];
    }

    // Insertion sort

    for(i = 1; i < lines; i++)
    {
        j = i;

        while(j > 0 && strcmp(output[j - 1], output[j]) > 0)
            ptemp = output[j - 1], output[j - 1] = output[j], output[j] = ptemp, j--;
    }

    // Write sorted lines to STDOUT

    for(i = 0; i < lines; i++)
        printf("%s", output[i]);
}

Platformy

Wszyscy wiemy, że maszyny typu big-endian są znacznie wydajniejsze niż ich odpowiedniki typu little-endian. Do testów porównawczych skompilujemy CleverSort z włączonymi optymalizacjami i losowo utworzymy ogromną listę (nieco ponad 100 000 ciągów) 4-bajtowych linii:

$ gcc -o cleversort -Ofast cleversort.c
$ head -c 300000 /dev/zero | openssl enc -aes-256-cbc -k '' | base64 -w 4 > input
$ wc -l input
100011 input

Benchmark Big-Endian

$ time ./cleversort < input > /dev/null

real    0m0.185s
user    0m0.181s
sys     0m0.003s

Niezbyt brudny.

Znak Little-Endian

$ time ./cleversort < input > /dev/null

real    0m27.598s
user    0m27.559s
sys     0m0.003s

Boo, mały Endian! Gwizd!

Opis

Sortowanie za pomocą wstawiania jest naprawdę dość wydajne w przypadku prawie posortowanych list, ale jest okropnie nieskuteczne w przypadku losowo sortowanych list.

Podstępną częścią CleverSort jest makro FIRSTSHORT :

#define FIRSTSHORT(N) *((uint16_t *) input[N])

Na maszynach big-endian uporządkowanie leksykograficzne ciągu dwóch 8-bitowych liczb całkowitych lub ich konwersja na 16-bitowe liczby całkowite i uporządkowanie ich później daje takie same wyniki.

Oczywiście jest to możliwe również na maszynach z małym endianem, ale makro powinno być

#define FIRSTSHORT(N) (input[N][0] | (input[N][1] >> 8))

który działa zgodnie z oczekiwaniami na wszystkich platformach.

Powyższy „test porównawczy big-endian” jest w rzeczywistości wynikiem użycia odpowiedniego makra.

Przy złym makrze i maszynie typu endian lista jest wstępnie sortowana według drugiego znaku każdej linii, co powoduje losowe uporządkowanie z leksykograficznego punktu widzenia. W tym przypadku sortowanie wstawiane zachowuje się bardzo słabo.

Python 2 vs. Python 3

Oczywiście Python 3 jest o kilka rzędów wielkości szybszy niż Python 2. Weźmy na przykład tę implementację algorytmu Shellsort :

Kod

import sys
from math import log

def shellsort(lst):

    ciura_sequence = [1, 4, 10, 23, 57, 132, 301, 701]  # best known gap sequence (Ciura, 2001)

    # check if we have to extend the sequence using the formula h_k = int(2.25h_k-1)
    max_sequence_element = 1/2*len(lst)
    if ciura_sequence[-1] <= max_sequence_element:
        n_additional_elements = int((log(max_sequence_element)-log(701)) / log(2.25))
        ciura_sequence += [int(701*2.25**k) for k in range(1,n_additional_elements+1)]
    else:
        # shorten the sequence if necessary
        while ciura_sequence[-1] >= max_sequence_element and len(ciura_sequence)>1:
            ciura_sequence.pop()

    # reverse the sequence so we start sorting using the largest gap
    ciura_sequence.reverse()

    # shellsort from http://sortvis.org/algorithms/shellsort.html
    for h in ciura_sequence:
        for j in range(h, len(lst)):
            i = j - h
            r = lst[j]
            flag = 0
            while i > -1:
                if r < lst[i]:
                    flag = 1
                    lst[i+h], lst[i] = lst[i], lst[i+h]
                    i -= h
                else:
                    break
            lst[i+h] = r

    return lst

# read from stdin, sort and print
input_list = [line.strip() for line in sys.stdin]
for line in shellsort(input_list):
    print(line)

assert(input_list==sorted(input_list))

Reper

Przygotuj wejście testowe. To pochodzi z odpowiedzi Dennisa, ale z mniejszą liczbą słów - Python 2 jest bardzo powolny ...

$ head -c 100000 /dev/zero | openssl enc -aes-256-cbc -k '' | base64 -w 4 > input

Python 2

$ time python2 underhanded2.py < input > /dev/null 

real    1m55.267s
user    1m55.020s
sys     0m0.284s

Python 3

$ time python3 underhanded2.py < input > /dev/null 

real    0m0.426s
user    0m0.420s
sys     0m0.006s

Gdzie jest podstępny kod?

Zakładam, że niektórzy czytelnicy mogą sami wytropić oszusta, więc ukryję odpowiedź za pomocą tagu spoiler.

Sztuką jest dzielenie liczb całkowitych w obliczeniach max_sequence_element. W Pythonie 2 1/2zwraca zero, a zatem wyrażenie jest zawsze równe zero. Jednak zachowanie operatora zmieniło się na podział zmiennoprzecinkowy w Pythonie 3. Ponieważ ta zmienna kontroluje długość sekwencji przerw, która jest krytycznym parametrem Shellsort, Python 2 używa sekwencji, która zawiera tylko numer jeden, podczas gdy Python 3 używa prawidłowej sekwencji. Powoduje to kwadratowy czas działania Python 2.

Premia 1:

Możesz naprawić kod, po prostu dodając kropkę po 1lub 2w obliczeniach.

Premia 2:

Przynajmniej na moim komputerze Python 2 jest nieco szybszy niż Python 3, gdy działa naprawiony kod ...