Il modo più veloce per ottenere il massimo valore da una gamma esclusiva in rubino

Question

Ok, quindi diciamo di avere una gamma davvero grande in rubino. Voglio trovare un modo per ottenere il valore massimo nell'intervallo.

L'intervallo è esclusivo (definito con tre punti) che significa che non include l'oggetto finale nei risultati. Può essere costituito da Integer, String, Time o qualsiasi oggetto che risponda a #<=> e #succ. (Che sono gli unici requisiti per l'oggetto di inizio/fine in Range)

Ecco un esempio di una gamma esclusiva:

past = Time.local(2010, 1, 1, 0, 0, 0) 
    now = Time.now 
    range = past...now 

    range.include?(now) # => false 

Ora so ho potuto solo fare qualcosa di simile per ottenere il valore massimo:

range.max # => returns 1 second before "now" using Enumerable#max 

Ma questo richiederà una quantità non trascurabile di tempo per l'esecuzione. So anche che potrei sottrarre 1 secondo da qualunque sia l'oggetto finale. Tuttavia, l'oggetto potrebbe essere diverso da Time e potrebbe non supportare nemmeno #-. Preferirei trovare una soluzione generale efficiente, ma sono disposto a combinare un codice caso speciale con una soluzione alternativa a una soluzione generale (ne parleremo più avanti).

Come accennato in precedenza utilizzando Range#last non funzionerà neanche, perché è un intervallo esclusivo e non include l'ultimo valore nei suoi risultati.

L'approccio più veloce che potevo pensare era questo:

max = nil 
    range.each { |value| max = value } 

    # max now contains nil if the range is empty, or the max value 

Questo è simile a quello che Enumerable#max fa (che Gamma eredita), tranne che sfrutta il fatto che ogni valore sarà maggiore del precedente, quindi possiamo saltare usando #<=> per confrontare ogni valore con il precedente (il modo in cui lo fa Range#max) risparmiando un po 'di tempo.

L'altro approccio a cui stavo pensando era di avere un codice di caso speciale per tipi di ruby ​​comuni come Integer, String, Time, Date, DateTime e quindi utilizzare il codice sopra come ripiego. Sarebbe un po 'brutto, ma probabilmente molto più efficiente quando si incontrano questi tipi di oggetto perché potrei usare la sottrazione da Range#last per ottenere il valore massimo senza alcuna iterazione.

Qualcuno può pensare a un approccio più efficiente/più veloce di questo?

Answer 1

La soluzione più semplice che mi viene in mente, che lavorerà per inclusive, nonché linee esclusive:

range.max 

di altre soluzioni possibili:

range.entries.last 
range.entries[-1] 

Queste soluzioni sono tutti O (n), e sarà molto lento per grandi distanze. Il problema in linea di principio è che i valori dell'intervallo in Ruby sono enumerati utilizzando il metodo succ in modo iterativo su tutti i valori, iniziando dall'inizio. Gli elementi non devono implementare un metodo per restituire il valore precedente (ad esempio pred).

Il metodo più veloce sarebbe quella di trovare il predecessore del l'ultimo elemento (un O (1) nella soluzione):

range.exclude_end? ? range.last.pred : range.last 

Questo funziona solo per gli intervalli che hanno elementi che implementano pred. Le versioni successive di Ruby implementano pred per i numeri interi. Devi aggiungere tu stesso il metodo se non esiste (essenzialmente equivalente al codice del caso speciale che hai suggerito, ma leggermente più semplice da implementare).

Un rapido analisi comparativa mostra che questo ultimo metodo è il più veloce di molti ordini di grandezza per le grandi catene (in questo caso range = 1...1000000), perché è O (1):

          user  system  total  real 
r.entries.last      11.760000 0.880000 12.640000 (12.963178) 
r.entries[-1]      11.650000 0.800000 12.450000 (12.627440) 
last = nil; r.each { |v| last = v } 20.750000 0.020000 20.770000 (20.910416) 
r.max        17.590000 0.010000 17.600000 (17.633006) 
r.exclude_end? ? r.last.pred : r.last 0.000000 0.000000 0.000000 ( 0.000062) 

Benchmark code is here.

Nei commenti si consiglia di utilizzare range.last - (range.exclude_end? ? 1 : 0). Funziona per le date senza metodi aggiuntivi, ma non funzionerà mai per intervalli non numerici. String#- non esiste e non ha senso con argomenti interi. String#pred, tuttavia, can be implented.

Answer 2

io non sono sicuro circa la velocità (e test iniziali non sembrano incredibilmente veloce), ma il seguente potrebbe fare quello che ti serve:

past = Time.local(2010, 1, 1, 0, 0, 0) 
now = Time.now 
range = past...now 

range.to_a[-1] 

test molto semplice (contando nella mia testa) ha mostrato che ci sono voluti circa 4 secondi mentre il metodo che hai fornito è durato circa 5-6. Spero che questo ti aiuti.

Modifica 1: è stata rimossa la seconda soluzione perché era completamente sbagliata.

Answer 3

Non riesco a pensare che ci sia un modo per ottenere ciò che non comporta l'enumerazione della gamma, almeno a meno che, come già menzionato, si abbiano altre informazioni su come verrà costruito l'intervallo e quindi si può inferire il valore desiderato senza enumerazione. Di tutti i suggerimenti, andrei con #max, poiché sembra essere più espressivo.

require 'benchmark' 
N = 20 
Benchmark.bm(30) do |r| 
    past, now = Time.local(2010, 2, 1, 0, 0, 0), Time.now 
    @range = past...now 
    r.report("range.max") do 
    N.times { last_in_range = @range.max } 
    end 
    r.report("explicit enumeration") do 
    N.times { @range.each { |value| last_in_range = value } } 
    end 
    r.report("range.entries.last") do 
    N.times { last_in_range = @range.entries.last } 
    end 
    r.report("range.to_a[-1]") do 
    N.times { last_in_range = @range.to_a[-1] } 
    end 
end 
           user  system  total  real 
range.max      49.406000 1.515000 50.921000 (50.985000) 
explicit enumeration   52.250000 1.719000 53.969000 (54.156000) 
range.entries.last    53.422000 4.844000 58.266000 (58.390000) 
range.to_a[-1]     49.187000 5.234000 54.421000 (54.500000) 

Ho notato che la 3a e la 4a opzione hanno aumentato significativamente il tempo di sistema. Mi aspetto che ciò sia legato alla creazione esplicita di un array, che sembra una buona ragione per evitarli, anche se ovviamente non sono più costosi nel tempo trascorso.