Quali linguaggi di programmazione forniscono una trasformazione Schwartziana come interfaccia per l'ordinamento

Naviga le tue risposte
2

Introduzione

La trasformazione di Schwartzian - anche conosciuta come map-sort-map o decorare-ordinamento-undecorato (DSU) -, attribuito a Randal Schwartz della comunità Perl , ordina gli elementi di un elenco o di un array in base a una metrica che associa ogni elemento al suo "valore di ordinamento".

Esempio per coloro che non hanno familiarità con la trasformazione di Schwartzian

Ad esempio in Python 2.4 e versioni successive, sia la funzione sorted() che il metodo sul posto list.sort() richiedono un parametro key che ci consente di fornire una speciale "funzione chiave" .

Questa funzione viene semplicemente chiamata su ogni elemento dell'elenco prima di effettuare confronti e quindi evita di calcolare il valore del criterio ogni volta in modo intelligente.

In altre parole, l'ordinamento di un elenco (Python) di stringhe maiuscole e minuscole: 

>>> sortList = ["the", "Schwartzian", "Transform", "rocks"]

>>> sortList.sort(key = lambda e: e.lower())
['rocks', 'Schwartzian', 'the', 'Transform']

Questo potrebbe anche essere suddiviso in 3 passaggi di base Schwartz suggerisce: 

#1:  Turn the list into an array of references to pairs
>>> temp = [(e.upper(), e) for e in sortList]
>>> temp
[('THE', 'the'), ... , ('TRANSFORM', 'Transform'), ('ROCKS', 'rocks')]

#2: Sort this list by the second elements
>>> temp.sort()

#3: Turn the sorted list back into one one value list
>>> sortList = [e[1] for e in temp]   
>>> sortList
['rocks', 'Schwartzian', 'the', 'Transform']

La domanda

Ora mi chiedo se altri linguaggi di programmazione ben noti come C ++, C # 1) , Java, JavaScript, VisualBasic e così via forniscano a Schwartzian anche la trasformazione come interfaccia o sia una "soluzione" (una propria implementazione piuttosto che una funzionalità linguistica), è necessario invece come questo esempio in C #: 

var unsorted = new string[] { "the", "Schwartzian", "Transform", "rocks"};
var sorted = unsorted.Select(word => new { word, lower = word.ToLower() })
                     .OrderBy(t => t.lower)
                     .Select(t => t.word)
                     .ToArray();

1) Per quanto ne so è possibile utilizzare la sintassi Linq

    
posta elegent 21.02.2016 - 01:00
fonte

4 risposte

2

C ++ normalmente usa < per specificare l'ordinamento e questo rende la sua interfaccia di ordinamento più complicata, ma ancora in qualche modo simile: 

std::sort(
    vec.begin(), vec.end(), [](auto s1, auto s2) { return to_lower(s1) < to_lower(s2); });

Nota inoltre che std::sort modifica la raccolta originale, non ne produce una nuova.

C # e VB.NET supportano questo direttamente, usando la sintassi che hai già usato: 

var sorted = unsorted.OrderBy(t => t.ToLower())
                     .ToArray();

Gli stream Java 8 utilizzano Comparator , che ha un'interfaccia simile a < in C ++. Ma fornisce anche Comparator.comparing() , che ti consente di specificare solo la chiave: 

List<String> sorted = unsorted.stream()
    .sorted(Comparator.comparing(s -> s.toLowerCase()))
    .collect(Collectors.toList());

Il Array.sort di JavaScript accetta un comparatore, proprio come Java, ma non ha alcuna funzione di aiuto. Il risultato è simile a C ++: 

arr.sort(
    function(a, b) { return a.toLocaleLowerCase().localeCompare(b.toLocaleLowerCase()); });

Per riassumere: mentre tutte le lingue che hai menzionato offrono una funzionalità simile, solo C #, VB.NET e, con una sintassi più dettagliata, Java ti permette di specificare solo la chiave fuori dalla scatola.

    
risposta data 21.02.2016 - 02:29
fonte
5

La trasformazione di Schwarzian è un modo per trasformare O (N) sui dati che vengono ordinati (un processo O (n log n)). Viene utilizzato per superare la necessità di eseguire conversioni 2 * O (n log n).

La parte 'decorare' del nome dello stile del pattern è anche conosciuta come memoization in cui i valori utilizzati di frequente vengono memorizzati nella cache.

Possiamo vedere cose simili fatte con hashCode in Java's String dove viene calcolato una volta e solo una volta.

Quindi, perché tutto questo pretesto e nessuna trasformazione di Schwarzian in altre lingue?

Prima di tutto, spesso i componenti per rendere questo idiomatico non ci sono. Gli stream non erano in Java fino all'1,8. Il @s = map { ... } sort { ... } map { ... } @u di perl è uno stile di flusso ottimizzato.

L'altra cosa è che ci sono altri modi idiomatici su cui lavorare.

Se hai una trasformazione di confronto costosa in Java, quindi crea un metodo privato che esegue la trasformazione una volta e memorizza quel valore, oppure se questo è un codice che non puoi modificare o sottoclasse (come String ) rendi una classe wrapper che (ad esempio) contiene la stringa stessa e il valore convertito in lettere minuscole.

Tutto torna alla parte - non è lì perché non era fattibile in modo pulito con le parti del linguaggio in un modo che è idiomatico, di esso è fattibile in un altro modo che non sembra uguale.

    
risposta data 21.02.2016 - 02:30
fonte
2

Penso che l'articolo di wikipedia che hai linkato nel post di apertura risponda davvero bene alla tua domanda. La trasformazione di Schwartz è un nome di un particolare idioma utilizzato in Perl per implementare uno specifico algoritmo semplice che ottimizza l'ordinamento precompilando le chiavi per ordinare. Come indicato nell'articolo, altre comunità potrebbero implementare lo stesso algoritmo in modi diversi, oppure potrebbero avere un nome diverso per lo stesso idioma.

Quindi, ci sono almeno tre condizioni che devono essere soddisfatte affinché una lingua e / o la sua comunità adottino la trasformazione schwartziana come un idioma:

  1. La lingua dovrebbe avere funzioni di ordine superiore come map e sort e un modo di comporre pipeline di tali funzioni,
  2. La lingua non dovrebbe già avere un modo migliore per ottenere lo stesso risultato,
  3. La comunità deve avere familiarità con il termine "trasformazione di schwartzian".

Il punto 1. ovviamente elimina le lingue senza HOF, come le versioni precedenti di Java, o le lingue in cui sono possibili le HOF, ma ingombrante e difficilmente idiomatico, come C e versioni precedenti di C ++. Nota che questo è il meccanismo che rende possibile l'implementazione di una pipeline schwartziana simile a trasformazioni per l'elaborazione di raccolte e molte lingue, da C # a Haskell, offrono e incoraggiano un simile stile di programmazione.

Il punto 2. elimina le lingue come C #, F # o Ruby con le loro varianti della funzione sortBy . La trasformazione di Schwartzian come un idioma non ha molto senso quando si ha una singola funzione che fa tutto il lavoro nella libreria standard della propria lingua (tale funzione può essere implementata o meno come una trasformazione schwartziana stessa). Nota come nel tuo esempio in C # sia Selects in effetti non necessario: hai solo bisogno di un OrderBy(x => x.ToLower()) per ottenere ciò di cui hai bisogno, rendendo l'intero idioma fuori luogo.

Per quanto riguarda il punto 3 - ovviamente è necessario conoscere il nome per usarlo, e io per primo non l'ho mai sentito prima. Impari qualcosa di nuovo ogni giorno;)

Quante lingue soddisfano tutti e tre i criteri? Non lo so. Ma è abbastanza probabile che solo Perl e Python (probabilmente una lingua con molti "expats" Perl) facciano.

    
risposta data 21.02.2016 - 03:30
fonte
1

È fattibile in C ++, tranne per il fatto che devi scrivere autonomamente la funzione di utilità.

In generale, se c'è qualcosa che si pensa manchi nella libreria standard C ++, è perché nessuno ha scritto una proposta per includerla in C ++ e sottoporla alla commissione per gli standard C ++.

Prima di C ++ 11, mancano alcune parti cruciali:

Anche con C ++ 11, manca ancora un bit cruciale:

  • Attualmente non è possibile vincolare l'argomento keyFunc come un funtore C ++ (oggetto funzione, lambda o un puntatore a funzione) che accetta un input di tipo T e restituisce un valore di tipo K .
    Se un programmatore passa qualcosa che non va bene, il compilatore stamperà solo un sacco di errori.

Ora che queste parti cruciali sono in C ++ 11, molti programmatori C ++ hanno pubblicato utili bit di codice template su Stack Overflow. Questi finiranno per "gocciolare" nella libreria degli standard C ++, se saranno giudicati utili e se qualcuno scriverà una proposta formale da sottoporre al comitato.

Implementazione di esempio in C ++ 11 - appena testata; si applicano le dichiarazioni di non responsabilità. 

template <typename T, class KeyFunc>
auto SchwartzianCPlusPlusMemoized( 
    const std::vector<T>& inputVector, 
    const KeyFunc& keyFunc) 
-> std::vector<T>
{
    typedef decltype(declval<KeyFunc>()(declval<T>())) K;
    typedef std::pair<K, const T*> P;
    std::vector<P> tempVector;
    for (const T& t : inputVector) {
        tempVector.emplace_back(keyFunc(t), &t);
    }
    auto lessFunc = [](const P& left, const P& right) -> bool {
        return (left.first < right.first);
    };
    std::sort(tempVector.begin(), tempVector.end(), lessFunc);
    std::vector<T> outputVector;
    for (const P& p : tempVector) {
        outputVector.emplace_back(*p.second);
    }
    return outputVector;
}
    
risposta data 21.02.2016 - 18:07
fonte

Leggi altre domande sui tag

Come può un computer arrotondare l'ultima cifra in una rappresentazione in virgola mobile? Perché il controllo degli errori bit bit è importante nei garbage collector?