Bottom line: problemi come questo possono spesso essere risolti attaccando una chiamata .array
subito prima della funzione offendente. Questo fornisce un buffer con funzionalità sufficienti per eseguire l'algoritmo.
Quello che segue è il ragionamento dietro la biblioteca e un paio di altre idee che è possibile utilizzare per implementare anche questo:
Il motivo per cui questo non compila ha a che fare con la filosofia std.algorithm e varia: che sono il più economici possibile per spingere le decisioni di costo al livello più alto.
In std.algorithm (e gli intervalli più ben scritti e gli algoritmi che consumano un intervallo), i vincoli del modello respingono qualsiasi input che non offra ciò di cui ha bisogno gratuitamente. Allo stesso modo, la trasformazione di intervalli, come filtro, splitter, ecc. Restituirà solo quelle funzionalità che possono offrire a costi minimi.
Rifiutandoli in fase di compilazione, costringono il programmatore a prendere la decisione al più alto livello su come vogliono pagare quei costi. Potresti riscrivere la funzione in modo diverso, potresti bufferizzarla autonomamente con una varietà di tecniche per pagare i costi in anticipo, o qualsiasi altra cosa tu possa trovare che funzioni.
Ecco cosa succede al tuo codice: readText
restituisce un array, che è un intervallo quasi completo. (Dal momento che restituisce un string
, fatto di UTF-8, in realtà non offre un accesso casuale per quanto riguarda Phobos (anche se, confondendo, il linguaggio stesso lo vede in modo diverso, cerca nei forum D la polemica "autodecode" se vuoi saperne di più) poiché trovare un code point Unicode in un elenco di caratteri utf-8 a lunghezza variabile richiede la scansione di tutto. Scansionare tutto non è un costo minimo, quindi Phobos non tenterà mai di farlo a meno che non lo chiedi espressamente).
In ogni caso, readText
restituisce una gamma con molte funzionalità, inclusa la salvabilità di cui ha bisogno il numero splitter
. Perché è necessario salvare splitter
? Considera il risultato che promette: una serie di stringhe che iniziano dall'ultimo punto di split e proseguono fino al prossimo punto di split. Che aspetto ha l'implementazione quando si scrive questo per un range più generico che può eventualmente fare a buon mercato?
Qualcosa in questo senso: prima, save
la posizione di partenza in modo da poterla restituire in seguito. Quindi, usando popFront
, avanzare attraverso di esso fino a trovare il punto di divisione. Quando lo fa, restituisci l'intervallo salvato fino al punto del punto di divisione. Quindi, popFront
oltre il punto di divisione e ripetere il processo fino a quando non si è consumato il tutto (while(!input.empty)
).
Quindi, dal momento che l'implementazione di splitter
ha richiesto la possibilità di save
il punto di partenza, richiede almeno un intervallo di inoltro (che è solo un intervallo salvabile.Andrei ora sente nominare cose come questa è un po 'sciocco perché ci sono così tanti nomi, ma al momento stava scrivendo std.algorithm
e credeva ancora nel dare loro tutti i nomi).
Non tutti gli intervalli sono in avanti! Gli array sono, salvarli è facile come restituire una fetta dalla posizione corrente. Anche molti algoritmi numerici, salvarli significa semplicemente mantenere una copia dello stato corrente. La maggior parte degli intervalli di trasformazione è salvabile se l'intervallo che stanno trasformando è salvabile; di nuovo, tutto ciò che devono fare è restituire lo stato corrente.
...... mentre scrivo questo, in realtà, penso che il tuo esempio sia essere salvabile. E, in effetti, c'è un sovraccarico che prende un predicato e compila!
http://dlang.org/phobos/std_algorithm_iteration.html#.splitter.3
import std.algorithm;
import std.array;
import std.stdio;
void main(string[] args)
{
auto t = "foo\n---\nbar"
.splitter('\n')
.filter!(e => e.length)
.splitter!(a => a == "---")
;
writeln(t);
}
uscita: [["foo"], ["bar"]]
Sì, è compilato e divisa su linee pari ad una cosa particolare. L'altro sovraccarico, .splitter("---")
, non riesce a compilare, perché quel sovraccarico richiede una funzionalità di slice (o una stringa ristretta, che Phobos rifiuta di tagliare genericamente ... ma sa che in realtà può essere comunque, quindi la funzione è di tipo speciale. in tutta la biblioteca.)
Ma, perché richiede l'affettatura invece del solo salvataggio? Onestamente, non lo so. Forse mi manca anche qualcosa, ma l'esistenza del sovraccarico che funziona mi implica che la mia concezione dell'algoritmo è corretta; it can può essere fatto in questo modo. Credo che tagliare le fette sia un po 'più economico, ma anche la versione di salvataggio è abbastanza economica (dovresti tenere conto del numero di oggetti che hai passato per arrivare allo splitter, quindi restituire saved.take(that_count)
.... forse è questo il motivo giusto : eseguiresti due volte l'iterazione sugli elementi, una volta all'interno dell'algoritmo, quindi di nuovo all'esterno, e la libreria ritiene che sia sufficientemente costoso puntare su un livello. (La versione predicativa aggira questo facendo la tua funzione esegue la scansione, e quindi Phobos non considera più il suo problema, tu sei a conoscenza di ciò che sta facendo la tua funzione.)
Posso vedere la logica in questo. Potrei andare su entrambi i lati, tuttavia, perché la decisione di eseguirlo di nuovo su di esso è ancora una volta ancora all'esterno, ma non capisco perché potrebbe non essere desiderabile fare a meno di qualche pensiero
Infine, perché lo splitter
non offre l'indicizzazione o l'analisi sull'output? Perché non lo offre anche lo filter
? Perché lo offre map
?
Bene, ha di nuovo a che fare con questa filosofia a basso costo. map
può offrirlo (supponendo che il suo input lo faccia) perché map
non modifica effettivamente il numero di elementi: il primo elemento nell'output è anche il primo elemento nell'input, solo con qualche funzione eseguita sul risultato. Idem per l'ultimo e tutti gli altri in mezzo.
filter
modifiche che però. Filtrando i numeri dispari di [1,2,3] restituisce solo [2]: la lunghezza è diversa e 2 è ora trovato all'inizio anziché al centro. Ma non puoi sapere dove è finché non applichi effettivamente il filtro - non puoi saltare senza bufferizzare il risultato.
splitter
è simile al filtro. Cambia la posizione degli elementi e l'algoritmo non conosce dove si divide fino a quando non esegue effettivamente gli elementi.In questo modo è possibile indicare come si esegue l'iterazione, ma non prima dell'iterazione, quindi l'indicizzazione sarebbe la velocità di O(n)
- troppo computazionalmente troppo costosa. L'indicizzazione dovrebbe essere estremamente economica.
In ogni caso, ora che abbiamo capito il motivo per cui il principio è lì - di farvi, il programmatore fine di prendere decisioni su cose costose come il buffering (che richiede più memoria di quanto è gratuito) o l'iterazione supplementare (che richiede più CPU tempo di quanto sia privo di costi all'algoritmo), e abbiamo qualche idea sul perché lo splitter
ne abbia bisogno pensando alla sua implementazione, possiamo guardare ai modi per soddisfare l'algoritmo: dobbiamo usare la versione che mangia qualche CPU in più cicla e scrivilo con la nostra funzione di confronto personalizzata (vedi esempio sopra), o fornisci l'affettatura in qualche modo. Il modo più semplice consiste nel buffering del risultato in una matrice.
import std.algorithm;
import std.array;
import std.file;
void main(string[] args)
{
auto t = args[1].readText()
.splitter('\n')
.array // add an explicit buffering call, understanding this will cost us some memory and cpu time
.split("---")
;
}
Si potrebbe anche tamponare localmente o qualcosa di se stessi per ridurre il costo della dotazione, ma comunque lo si fa, il costo deve essere pagato da qualche parte e Phobos si preferisce il programmatore, che capisce le esigenze della vostra programma e se siete disposti a pagare o meno questi costi, prendere quella decisione anziché pagarla per vostro conto senza dirvelo.
Ottima risposta. Grazie. – sigod