Which one of these two is better (more efficient)?
Non hai veramente definito ciò che intendi per "efficiente", ma d'altra parte, il tuo problema reale è un po 'più complesso di quello che hai descritto.
Sarei interessato ad avere maggiori dettagli, se possibile.
Dato che non ci sono requisiti specifici di temporizzazione o utilizzo della memoria, né chiari limiti esterni sui tuoi input, il problema è un po 'troppo generico: non dovresti davvero preoccuparti di quale opzione sia più efficiente.
Vediamo, ad esempio, la peggiore complessità del caso:
- Opzione 1: O (n) ora, O (n) spazio
- Opzione 2: O (n) ora, O (n) spazio
Io ora più di una persona che direbbe all'istante:
" Se è lineare, non sprecare il tuo tempo con esso! "
Ora, praticamente, l'opzione 2 potrebbe sembrare più interessante perché:
- devi solo eseguire il ciclo una sola volta sui tuoi dati e,
- per la maggior parte delle persone (me compreso), la rappresentazione mentale di come viene eseguito il calcolo presuppone che sia meglio calcolare tutto in un unico passaggio anziché eseguire più passaggi (perché l'attraversamento di un elenco potrebbe richiedere un sovraccarico); quel modello non prende necessariamente in considerazione vincoli esterni come I / O, memoria, cache e così via, e come interagiscono. In effetti, trovo davvero difficile sapere in anticipo quale sia l'opzione migliore, in generale. Tuttavia, più passaggi sono un ottimo modo per separare il lavoro in blocchi leggibili (ad esempio, vedi come i compilatori non provano a fare tutto in una volta).
Se hai alcune prove obiettive che devi ottimizzare quella parte, sperimenta e misura per una metrica specifica con input rappresentativi.
Which would you use and why?
Vorrei usare l'Opzione 1, principalmente per Keep It Simple, Stupid , e anche perché non c'è apparente ragione per cui "l'efficienza" è fondamentale qui.
L'opzione 1 è leggibile, facile da capire, facile da gestire.
Do you think there is a better solution than these?
"Meglio" è ugualmente difficile da comprendere, qui, per gli stessi motivi di cui sopra.
Ma se supponiamo che "Opzione 2" sia decisamente migliore di "Opzione 1", allora l'opzione 2 può essere ancora più efficace:
Non appena incontri il 1988 o il 1989, smetti di compilare il secondo elenco.
Quindi, non memorizzerai più di N elementi (in entrambi gli elenchi di output), se la tua lista di input ha N elementi.
Per il gusto di farlo, ecco un'implementazione di prototipo in Common Lisp. Ricorda, non raccomando questo approccio, personalmente rimango personalmente con l'Opzione 1.
Per prima cosa, ecco alcune sequenze di test (incluse le tue):
(defparameter *test*
'(((c 1990) (x 1990))
((a 1989) (b 1988) (c 1990))
((a 1990) (b 1985) (c 1998))
((a 1990) (b 1985) (c 1988))
((1 1990) (2 1981) (3 1983) (4 1993) (5 1981) (6 1985) (7 1990))
((1 1990) (2 1981) (3 1983) (4 1993) (5 1981) (6 1989) (7 1990))
((1 1988) (2 1988) (3 1982) (4 1995) (5 1989) (6 1989) (7 1990))))
Ecco un'opzione modificata 2 che non raccoglie elementi "1990" se alcuni elementi attuali o precedenti erano membri di {1988,1989}:
(defun option-2 (pair-list)
(loop for (name year) in pair-list
for member-p = (member year '(1989 1988) :test #'eql)
for some-member-p = member-p then (or some-member-p member-p)
when member-p
collect (list name year) into bag-a
when (and (not some-member-p) (eql year 1990))
collect (list name year) into bag-b
finally (return (if some-member-p bag-a bag-b))))
(mapcar #'option-2 *test*)
=> (((C 1990) (X 1990)) ((A 1989) (B 1988)) ((A 1990)) ((C 1988))
((1 1990) (7 1990)) ((6 1989)) ((1 1988) (2 1988) (5 1989) (6 1989)))
Per un confronto, ecco l'Opzione 1. È più facile da capire, IMHO:
(defun option-1 (pair-list)
(or (remove-if-not (lambda (x) (member x '(1989 1988) :test #'eql))
pair-list :key #'second)
(remove-if-not (lambda (x) (eql x 1990))
pair-list :key #'second))))
(mapcar #'option-1 *test*)
=> (((C 1990) (X 1990)) ((A 1989) (B 1988)) ((A 1990)) ((C 1988))
((1 1990) (7 1990)) ((6 1989)) ((1 1988) (2 1988) (5 1989) (6 1989)))