Il mio algoritmo è troppo lento

0

Ripubblicato da Stack Overflow - Penso che questo è un posto più appropriato per porre la domanda.

Ho un algoritmo che per un intero x e un intero iniziale i tale che 1 < i < x il successivo valore di i è calcolato da i = floor(x / i) + (x mod i) . Questo continua fino a raggiungere un i che abbiamo già visto.

In JavaScript (anche se questa domanda è indipendente dal linguaggio):

function f(x, i) {
    var map = {};
    while(!map[i]) {
        map[i] = true;
        i = Math.floor(x / i) + (x % i); // ~~(x / i) is a faster way of flooring
    }
    return i;
}

Posso provare che alla fine raggiungeremo un i che abbiamo già visto, ma mi chiedo:

  1. C'è un modo più efficiente di calcolare il prossimo i ?
  2. (Ancora più importante) Esiste un modo per calcolare l'ennesimo i senza eseguire il ciclo n volte?

Giusto per chiarire - So che ci sono modi più veloci di usare le mappe hash JS per quel controllo, e che il pavimento può essere sostituito dalla divisione intero in altre lingue. Ho fatto entrambe le ottimizzazioni, ma le ho lasciate fuori per cercare di rendere il codice più facile da capire.

    
posta winhowes 27.04.2016 - 08:56
fonte

1 risposta

4

La tua dimostrazione che otterrai sempre un "i" precedentemente usato sembra implicare che la tua funzione di mappatura sia miscelazione topologica . Questo a sua volta suggerisce che la tua funzione è probabilmente caotica. Se è caotico, quindi per definizione non esiste un modo più rapido per produrre il risultato rispetto all'iterazione della funzione di mappatura.

Guardando in modo meno rigoroso, la funzione modulo ha la proprietà di prendere piccole differenze ed espandendole (rispetto alla dimensione del risultato) mentre la divisione intera prende grandi differenze e le riduce. Queste due proprietà si trovano comunemente nelle funzioni caotiche (ad esempio l'attrattore di Lorentz), quindi è suggestivo che la tua funzione possa essere caotica.

    
risposta data 27.04.2016 - 09:52
fonte

Leggi altre domande sui tag