Modi per usare un doppio come chiave in un set/mappa std

Il problema di usare i doppi come chiavi nelle mappe/insiemi è la precisione in virgola mobile.Modi per usare un doppio come chiave in un set/mappa std

Alcune persone hanno suggerito di aggiungere un epsilon nella funzione di confronto, ma ciò significa che le chiavi non soddisfano più il criterio rigoroso debole. Ciò significa che otterrai un set/mappa diverso a seconda dell'ordine di inserimento dei tuoi elementi.

Nel caso in cui si desidera aggregare/combinare/unire dati basati su valori doppi e sono disposti a consentire un certo livello di arrotondamento/epsilon (chiaramente, sarà necessario), la seguente soluzione è buona idea?

Convertire tutti i doppi (dove intendevamo come chiavi) in numeri interi moltiplicandoli per il fattore di precisione (ad esempio 1e8) e arrotondando al numero intero più vicino (int)i+0.5 (se i> 0), quindi creare un set/mappa che chiavi fuori da questi numeri interi. Quando si estraggono i valori finali delle chiavi, dividere i pollici per il fattore di precisione per ottenere il doppio valore indietro (anche se arrotondato).

fonte

2015-06-29 zhaomin

Forse è sufficiente utilizzare un tipo di dati di libreria arbitraria di precisione (ad esempio GMP) come tipo di chiave? – PaulMcKenzie

Perché consideri la precisione a virgola mobile un problema quando utilizzi i doppi come una chiave in una struttura ad albero o in una tabella hash? Funziona fin tanto che non si usano i NaN come chiavi, e funziona anche esattamente come ci si aspetterebbe. – tmyklebu

Mi chiedo quale tipo di problema possa richiedere valori in virgola mobile in insiemi o mappe. Gli insiemi e le mappe sono adatti per i dati discreti, i valori a virgola mobile sono buoni per i dati continui. –

"Convertire tutte le doppie (dove abbiamo inteso come chiavi) in interi moltiplicandoli per il fattore di precisione (ad esempio 1e8) e arrotondamento al numero intero più vicino (int)i+0.5 (se i> 0), quindi creare un set/mappa le chiavi da questi numeri interi.Quando si estraggono i valori finali delle chiavi, dividere gli interi per il fattore di precisione per ottenere il doppio valore indietro (anche se arrotondato). "

mi consiglia di utilizzare chiavi tipo intero (ad esempio long long) per la carta in primo luogo, e finiture per letto rappresentazione tramite una precisione fissa per la divisione.

Ma ciò dipende, se è possibile applicare fix point math per il proprio caso di utilizzo effettivo. Se è necessario coprire un'ampia gamma di precisioni del valore (ad esempio + -1e-7 - + -1e7), tale approccio non funzionerà.

fonte

2015-06-29 17:10:41

grazie per il suggerimento, ma in che modo esattamente è diverso dalla mia soluzione (scusa che non l'ho capito). stai suggerendo di usare le chiavi integer (ridimensionate e arrotondate come suggerito?) nella mappa e diviso per la stessa scala per ottenere il doppio valore? – zhaomin

@zhaomin Non c'è molta differenza in ciò che stavi descrivendo, volevo solo incoraggiarti ad andare in quella direzione. Si noti inoltre che i valori fissi in virgola mobile possono essere facilmente incapsulati in una classe. C'è anche un'implementazione standard per farlo: ['std :: ratio'] (http://en.cppreference.com/w/cpp/numeric/ratio) –

grazie. sfortunatamente sto cercando di ottenere questi numeri durante il runtime, quindi std :: ratio non funzionerà. ma grazie per il suggerimento – zhaomin

convertire tutte le doppie (dove abbiamo inteso come chiavi) in numeri interi moltiplicandoli per il fattore di precisione (ad esempio 1e8) e arrotondamento al il più vicino intero (int) i + 0.5 (se i> 0) , quindi creare un set/mappare le chiavi su questi numeri interi. Quando si estraggono i valori finali delle chiavi, divide gli interi del fattore di precisione per riportare il valore doppio (anche se arrotondato).

Invece di dividere per il fattore di precisione per ottenere il doppio di nuovo, semplicemente memorizzare il doppio insieme con il valore associato a una struttura, e mettere che struct nel dizionario come "valore" per quel tasto intero. In questo modo, il valore doppio originale è ancora disponibile e può essere utilizzato per i calcoli. Non solo per la ricerca della chiave.

Se, tuttavia, è possibile vivere con valori leggermente arrotondati (poiché si divide semplicemente un numero intero con un epsilon), l'approccio suggerito è già sufficiente.

Come l'altra risposta dice, dipende molto dalla gamma dei valori. Se alcuni sono estremamente grandi e altri sono estremamente piccoli, il tuo approccio per ottenere chiavi intere non funzionerà. Se sono solo alcune cifre a parte, allora potrebbe.

fonte

2015-06-30 13:48:22

grazie per il suggerimento. In realtà preferirei usare il valore arrotondato perché rappresenta meglio l'insieme di doppi che si arrotondano ad esso, piuttosto che scegliere il primo doppio che è stato messo nel set. – zhaomin

Modi per usare un doppio come chiave in un set/mappa std

risposta

Problemi correlati