Buona struttura dati per la conversione dell'unità?

Question

Folla StackOverflow. Ho una domanda sul design del software molto aperta.

Sono stato alla ricerca di una soluzione elastica per questo per un po 'e mi chiedevo se qualcuno qui avesse qualche idea brillante del problema. Considera questo come un puzzle di strutture dati.

Quello che sto cercando di fare è creare un convertitore di unità in grado di convertire da qualsiasi unità a qualsiasi unità. Supponiamo che il lexing e l'analisi siano già stati eseguiti. Alcuni semplici esempi:

Convert("days","hours")   // Yields 24 
Convert("revolutions", "degrees") // Yields 360 

per rendere le cose un po 'più complicato, si deve gestire senza problemi le ambiguità tra gli ingressi:

Convert("minutes","hours")  // Yields (1/60) 
Convert("minutes","revolutions") // Yields (1/21600) 

per rendere le cose ancora più divertente, si deve gestire le unità complesse senza bisogno di enumerare tutte le possibilità:

Convert("meters/second","kilometers/hour") 
Convert("miles/hour","knots") 
Convert("Newton meters","foot pounds") 
Convert("Acre feet","meters^3") 

Non c'è una risposta giusta o sbagliata, sto cercando idee su come ottenerlo. C'è sempre una soluzione di forza bruta, ma voglio qualcosa elegante che sia semplice e scalabile.

Answer 1

vorrei iniziare scegliendo un'unità standard per ogni quantità (ad es. Metri per la lunghezza, newton per forza, ecc) e quindi la memorizzazione di tutti i fattori di conversione di tale unità in una tabella

poi andare da giorni ad ore, ad esempio, trovi i fattori di conversione per secondi al giorno e secondi all'ora e li dividi per trovare la risposta.

per le ambiguità, ogni unità può essere associata a tutti i tipi di quantità che misura e per determinare quale conversione fare, si prenderà l'intersezione di questi due tipi di tipi (e se si rimane con 0 o più di uno sputeresti un errore)

Answer 2

Vorrei iniziare con una tabella di ricerca hash (o persistente - la tua scelta come implementare) che trasporta le conversioni di unità tra il numero di coppie che vuoi mettere. Se metti in ogni coppia possibile, allora questo è il tuo approccio alla forza bruta.

Se si dispone solo di coppie parziali, è possibile eseguire una ricerca tra le coppie che si trovano per trovare una combinazione. Per esempio, diciamo che ho queste due voci nella mia tabella hash:

Feet|Inches|1/12 
Inches|Centimeters|2.54 

Ora, se voglio convertire piedi per centimetri, ho una semplice ricerca su grafico: i vertici sono piedi, pollici e centimetri, e bordi sono i fattori di conversione 1/12 e 2.54. La soluzione in questo caso sono i due bordi 1/12, 2,54 (combinati tramite moltiplicazione, ovviamente). Se lo desideri, puoi ottenere più fantasia con i parametri del grafico.

Un altro approccio potrebbe essere l'applicazione del ragionamento abduttivo: esaminare i testi AI relativi ai risolutori algebrici per questo ...

Edit: indirizzamento unità composte

problema semplificata: convertire "Acri" a "Metri^2"

In questo caso, i tasti sono comprendendo che stiamo parlando di unità di lunghezza, in modo da perché non inseriamo una nuova colonna nella tabella per il tipo di unità , che può essere "lunghezza" o "area". Ciò aiuterà le prestazioni anche nei casi precedenti in quanto ti offre una colonna facile per abbattere lo spazio di ricerca.

Ora il trucco è capire quella lunghezza^2 = area. Perché non aggiungere un altro di ricerca che memorizza questi metadati:

Area|Length|Length|* 

Abbiamo Coppia questo con la tabella di unità primaria:

Meters|Feet|3.28|Length 
Acres|Feet^2|43560|Area 

Quindi l'algoritmo va:

• Solution è m^2, che è m * m, che è una lunghezza * lunghezza.
• L'input è acri, che è un'area.
• Cerca la meta tabella per m, e trova la lunghezza * mappatura lunghezza. Si noti che in esempi più complessi possono esserci più di una mappatura valida.
• Aggiungi alla soluzione una conversione Acri-> Piedi^2.
• Eseguire la ricerca del grafico originale per Piedi-> M.

Nota che:

• L'algoritmo non saprà se utilizzare area o lunghezza come il dominio di base in cui lavorare. Puoi fornire suggerimenti o lasciarli cercare in entrambi gli spazi.
• Il meta-tavolo diventa un po 'brute-force-ish.
• Il meta-tavolo dovrà diventare più intelligente se si inizia a mescolare i tipi (ad esempio Resistance = Voltage/Current) o si fa qualcosa di veramente brutto e si miscelano i sistemi di unità (ad esempio FooArea = Meters * Feet).

Answer 3

Presumo che si desidera conservare i dati sulla conversione in una sorta di tripli (fstUnit, sndUnit, multiplier).

Per conversioni di unità singole: utilizzare alcune funzioni di hash in O(1) per cambiare lo stucture unità a un certo numero, e poi mettere tutti i moltiplicatori in una matrice (basta ricordare la parte in alto a destra, perché la riflessione è il stesso, ma invertito).

Per casi complessi: Esempio 1. Da m/s a ​​km/h. Controlli (m, km) nella matrice, quindi (s, h), quindi moltiplica i risultati. Esempio 2. m^3 a km^3. Controlli (m, km) e portalo alla terza potenza.

Ovviamente alcuni errori, quando i tipi non corrispondono come campo e volume.

Answer 4

È possibile creare una classe per le unità che prendono il fattore di conversione e gli esponenti di tutte le unità di base (suggerirei di utilizzare unità metriche per questo, che semplificano la vita). Per esempio.in Pseudo-Java:

public class Unit { 
    public Unit(double factor, int meterExp, int secondExp, int kilogrammExp ... [other base units]) { 
    ... 
    } 
} 

//you need the speed in km/h (1 m/s is 3.6 km/h): 
Unit kmPerH = new Unit(1/3.6, 1, -1, 0, ...) 

Answer 5

Qualunque sia la struttura che si sceglie, e la vostra scelta può ben essere indicato dal vostro implementazione preferita (??? OO funzionale tabella DBMS) Penso che è necessario per identificare la struttura delle unità stesse.

Ad esempio una misura di 1000 km/h ha diversi componenti:

• una grandezza scalare, 1000;
• un prefisso, in questo caso kilo; e
• una dimensione, in questo caso L.T^(- 1), cioè, la lunghezza divisa per tempo.

tuo modellazione delle misure con le unità ha bisogno di catturare almeno questa complessità.

Come è già stato suggerito, si dovrebbe stabilire ciò che il set di base di unità che si intende utilizzare sono, e le unità SI di base suggeriscono immediatamente se stessi. Le strutture dei dati per le unità di modellazione verranno quindi definite in termini di tali unità di base. Si potrebbe quindi definire una tabella (pensando RDBMS qui, ma facilmente traducibile in l'implementazione preferita) con le voci quali:

unit name  dimension     conversion to base 

foot   Length     0.3048 
gallon(UK)  Length^3     4.546092 x 10^(-3) 
kilowatt-hour Mass.Length^2.Time^(-2) 3.6 x 10^6 

e così via. Avrete anche bisogno di una tabella di tradurre i prefissi (kilo-, nano-, mega-, mibi- ecc) in fattori moltiplicatori, e un tavolo di unità di base per ciascuna delle dimensioni (cioè metro è l'unità di base per la lunghezza, la seconda per il tempo, ecc.). Dovrete anche fare i conti con le unità quali feet che sono semplicemente sinonimi di altre unità.

Lo scopo della dimensione è, ovviamente, quello di garantire che le conversioni e altre operazioni (come l'aggiunta di 2 feet a 3.5 metres) siano commisurate.

E, per ulteriori letture, suggerisco this book by Cardarelli.

EDIT in risposta ai commenti ...

sto cercando di girare lontano dal suggerire soluzioni (specifiche di implementazione) quindi mi Waffle un po 'di più. Le unità composte, come i kilowattora, rappresentano un problema. Un approccio potrebbe essere quello di etichettare le misurazioni con più quote espressioni, come ad esempio kilowatt e hour, e una regola per combinare loro, in questo caso multiplication Ho potuto vedere questo diventando piuttosto peloso abbastanza rapidamente. Potrebbe essere meglio per limitare l'insieme valido di unità da quelli più comuni nel dominio dell'applicazione.

Per quanto riguarda le misurazioni in unità miste, lo scopo di definire la dimensione di un'unità è di fornire alcuni mezzi per garantire che solo le operazioni sensibili possano essere applicate alle misurazioni con unità. Quindi, è ragionevole aggiungere due lunghezze (L + L) insieme, ma non una lunghezza (L) e un volume (L^3). D'altra parte è ragionevole dividere un volume per una lunghezza (per ottenere un'area (L^2)). Ed è una specie di fino l'applicazione per determinare se le unità strani come ad esempio chilowattora per metro quadrato sono validi.

Infine, il libro I link enumera tutte le possibilità, immagino che le applicazioni più sensate con le unità implementeranno solo una selezione.

Answer 6

avrei una tabella con questi campi:

conversionID 
fromUnit 
toUnit 
multiplier 

e comunque il numero di righe è necessario memorizzare tutte le conversioni che si desidera supportare

Se si vuole sostenere un processo multi-step (gradi F a C), avreste bisogno di una relazione uno-a-molti con la tabella di unità, diciamo chiamato conversionStep, con campi come

conversionID 
sequence 
operator 
value 

Se si desidera memorizzare una serie di Conversi on ma il supporto conversioni più fasi, come la memorizzazione

Feet|Inches|1/12 
Inches|Centimeters|2.54 

e sostenere la conversione da piedi a centimetri, avrei memorizzare un piano di conversione in un'altra tabella, come

conversionPlanID 
startUnits 
endUnits 
via 

la riga sarà simile

1 | feet | centimeters | inches