Reverse subarray di un array con O (1)

-1

Ho un'idea di come implementare il sub array reverse con O (1), escludendo il calcolo preliminare come la lettura dell'input. Avrò molte operazioni inverse e non posso usare la soluzione banale di O (N).

Modifica: Per essere più chiaro, voglio costruire una struttura dati dietro l'array con un livello di accesso che sappia invertire le richieste e inverta la logica di indicizzazione quando è necessario che venga eseguita un'iterazione sull'array.

Modifica 2: la struttura dei dati verrà utilizzata solo per le iterazioni

Ho letto questo e questo e anche questa domande ma non aiutano.

Ci sono 3 casi che devono prendersi cura di:

  • Operazione inversa regolare
  • Inverti quella area inversa
  • Intersezione tra inverso e parte di un'altra area inversa nell'array

Ecco la mia implementazione per le prime due parti, avrò bisogno del tuo aiuto con l'ultima.

Questa è la classe della regola:

class Rule {
    public int startingIndex;
    public int weight;
}

È usato nella mia struttura dati di base Città:

public class City {
    Rule rule;
    private static AtomicInteger _counter = new AtomicInteger(-1);
    public final int id = _counter.incrementAndGet();

    @Override
    public String toString() {
        return "" + id;
    }
}

Questa è la classe principale:

public class CitiesList implements Iterable<City>, Iterator<City> {

    private int position;
    private int direction = 1;
    private ArrayList<City> cities;
    private ArrayDeque<City> citiesQeque = new ArrayDeque<>();
    private LinkedList<Rule> rulesQeque = new LinkedList<>();


    public void init(ArrayList<City> cities) {
        this.cities = cities;
    }

    public void swap(int index1, int index2){
        Rule rule = new Rule();
        rule.weight = Math.abs(index2 - index1);
        cities.get(index1).rule = rule;
        cities.get(index2 + 1).rule = rule;
    }

    @Override
    public void remove() {
        throw new IllegalStateException("Not implemented");
    }

    @Override
    public City next() {
        City city = cities.get(position);
        if (citiesQeque.peek() == city){
            citiesQeque.pop();
            changeDirection();
            position += (city.rule.weight + 1) * direction;
            city = cities.get(position);
        }
        if(city.rule != null){
            if(city.rule != rulesQeque.peekLast()){
                rulesQeque.add(city.rule);
                position += city.rule.weight * direction;
                changeDirection();
                citiesQeque.push(city);
            }
            else{
                rulesQeque.removeLast();
                position += direction;
            }
        }
        else{
            position += direction;
        }
        return city;
    }

    private void changeDirection() {
        direction *= -1;
    }

    @Override
    public boolean hasNext() {
        return position < cities.size();
    }

    @Override
    public Iterator<City> iterator() {
        position = 0;
        return this;
    }

}

Ed ecco un esempio di programma:

public static void main(String[] args) {
        ArrayList<City> list = new ArrayList<>();
        for(int i = 0 ; i < 20; i++){
            list.add(new City());
        }
        CitiesList citiesList = new CitiesList();
        citiesList.init(list);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        citiesList.swap(4, 8);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        citiesList.swap(2, 15);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
    }

Come gestisco le intersezioni inverse?

    
posta Ilya Gazman 31.10.2013 - 13:20
fonte

5 risposte

5

Potresti utilizzare una variante xor linked list (utilizzando gli indici in una matrice per il puntatore).

Quindi l'inversione è semplice:

reverse(int city1prev, int city1index, int city2prev, int city2index)
{

    int city1next = array[city1index].ptr^city1prev;
    int city2next = array[city2index].ptr^city2prev;

    city1.ptr = city2next^city1next;
    city2.ptr = city2prev^city1prev;

    array[city1prev].ptr^= city1index^city2index;
    array[city2next].ptr^= city1index^city2index;

}

Lo svantaggio è (come con tutte le implementazioni di elenchi collegati) che l'indicizzazione in esso è O (n).

Ciò invertirà il sottararray a causa di come funziona il collegamento xor: city2 sarà dove città1 era e city2prev sarà dopo di esso e così via. Quindi la nuova sequenza diventa: city1prev, city2, city2prev,..., city1next, city1, city2next .

Il punto chiave è che non vi è alcuna differenza tra l'attraversamento di una lista collegata xor in avanti o all'indietro (si mantiene un indice per gli elementi corrente e precedente e si ottiene il successivo facendo array[current].ptr^previous ).

    
risposta data 31.10.2013 - 15:17
fonte
6

Non ha senso cercare un meccanismo efficiente per effettivamente invertire le cose in un array più e più volte. Non puoi mai scendere al di sotto della complessità lineare, perché devi toccare (quasi) tutti gli elementi nel sottoinsieme.

Ciò che puoi fare è incapsulare la tua struttura dati dietro un livello di accesso che sa di invertire le richieste e inverte la logica di indicizzazione, se necessario, quando qualcuno vuole iterare sulla matrice. Ciò può farti prestazioni quasi normali anche per gli array parzialmente invertiti, finché il numero di richieste di inversione è piccolo , cioè la logica di ricerca aggiuntiva non è più costosa degli accessi alla memoria che salva tu. La rapidità con cui questo punto viene raggiunto dipende in gran parte da circostanze come la dimensione effettiva dei tuoi array, i probabili pattern di accesso, ecc.

    
risposta data 31.10.2013 - 14:03
fonte
1

Penso che quello che stai cercando sia un grafico non orientato. Se utilizzi una rappresentazione dell'elenco di adiacenze per memorizzare il percorso, allora se scambi due link nel percorso (perché erano incrocio), è necessario aggiornare l'elenco di adiacenza per i quattro nodi che si stanno influenzando.

Questa è un'operazione a tempo costante - non importa quanto grande sia il percorso, non importa quanti collegamenti tra i nodi, devi solo cambiare i quattro nodi che stai influenzando.

Inoltre, potrebbe essere possibile rappresentare i collegamenti come un sistema di equazioni lineari. Se ci sono soluzioni al sistema di equazioni, ci sono collegamenti che attraversano. Non citarmi su questo - dovrai chiedere a matematici migliori di me come faresti a fare questo. In questo modo non avrai bisogno di O (n ^ 2) per verificare gli incroci.

Un altro modo è disporre di due array che memorizzano rispettivamente la latitudine e la longitudine dei nodi. Prendi il sottoinsieme A di nodi che si trova entro la latitudine +/- della lunghezza L del link che stai attualmente controllando. Fai lo stesso con la longitudine e il set di caratteri B. L'insieme C che è l'intersezione di A e B è l'insieme di nodi che sono abbastanza vicini da disturbare il controllo.

LatArray = array ordinato di latitudini dei nodi

LongArray = array ordinato di longitudini di nodi

L = lunghezza del link corrente che stai controllando

A = Il set di nodi da LatArray che sono in latitudine +/- L del primo nodo del link che stai controllando

B = Il set di nodi da LongArray che sono in longitudine +/- L del primo nodo del link che stai controllando

C = intersezione di insiemi A e B

D = Come C , ma per il secondo nodo del link che stai controllando

Quanto sopra è un modo rapido per determinare quali altri nodi devono essere controllati perché si trovano nell'intervallo del link corrente. La funzione di ricerca per LatArray e LongArray può essere binaria.

Quanto sopra diventa utile quando hai a che fare con milioni di nodi.

Tuttavia, sii avvisato che l'algoritmo che ti colleghi a qui non è sufficiente per garantire buoni percorsi. Solo perché una rotta ottimale non ha intersezioni, non significa che se una rotta non ha intersezioni è ottimale.

Qualcosa come L'algoritmo di Clarke-Wright è probabilmente più vicino a quello che stai cercando. C'è una spiegazione e un libro di testo con più background qui:

risposta data 31.10.2013 - 16:13
fonte
1

Utilizzando l'idea strana di ratchet con xor elenco collegato , sono arrivato alla mia implementazione Java con O (1) tempo di complessità per la rotazione dell'array secondario non incluso il calcolo preliminare (come la lettura dell'input).

Chiamo questa struttura dati Elenco collegato diretto.

public class Node {
    Node next = null;
    Node previous = null;


    Node getNext(Node node){
        if(node == next){
            return previous;
        }

        if(node == previous){
            return next;
        }

        throw new IllegalStateException("How did you got here?");
    }

    void setNext(Node node, Node next){
        if(node == previous){
            previous = next;
        }
        else if(node == this.next){
            this.next = next;
        }
        else{
            throw new IllegalStateException("How did you got here?");
        }
    }
}

DirectedLinkedList class

public class DirectedLinkedList implements Iterable<Node>, Iterator<Node> {

    private Node head = new Node();
    private Node tail = head;
    private Node current;
    private Node previuse;

    @Override
    public Iterator<Node> iterator() {
        prepareForIteration();
        return this;
    }

    public void addToHead(Node node) {
        Node next = head.getNext(null);
        Node previuse = head.getNext(next);
        head.setNext(previuse, node);
        node.setNext(null, head);
        head = node;
    }

    public void swap(Node a, Node i, Node c, Node j){
        System.out.println("Swaping " + i + " , " + j);
        Node jNext;

        jNext = j.getNext(c);
        jNext.setNext(j, i);

        j.setNext(jNext, a);
        i.setNext(a, jNext);

        a.setNext(i, j);

        System.out.println();

    }

    private void prepareForIteration() {
        current = head;
        previuse = null;
    }

    @Override
    public boolean hasNext() {
        return current != tail;
    }

    @Override
    public Node next() {
        Node tmp = previuse;
        previuse = current;
        current = current.getNext(tmp);
        return previuse;
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub

    }
}

Ed ecco un programma di esempio: Io uso City for Node

public class City extends Node{
    private static AtomicInteger _counter = new AtomicInteger(-1);
    public final int id = _counter.incrementAndGet();

    @Override
    public String toString() {
        return "" + id;
    }
}

principale

public class Sample{

    private static DirectedLinkedList directedLinkedList;

    public static void main(String[] args) {
        directedLinkedList = new DirectedLinkedList();
        ArrayList<City> list = new ArrayList<City>();

        for (int i = 0; i < 20; i++) {
            City city = new City();
            directedLinkedList.addToHead(city);
            list.add(city);
        }

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        swap(4, 8);

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        swap(6, 12);

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
    }

    private static void swap(int i, int j) {
        Node a = null, b = null, c = null, d = null;

        int count = 0;
        for (Node city : directedLinkedList) {
            if (count == i) {
                a = city;
            }
            else if (count == i + 1) {
                b = city;
            }
            else if (count == j) {
                c = city;
            }
            else if (count == j + 1) {
                d = city;
            }
            count++;
        }

        directedLinkedList.swap(a, b, c, d);
    }
}
    
risposta data 01.11.2013 - 13:22
fonte
0

Bene, per quanto riguarda O (N) per attraversamento, O (1) per inversione, ma con uno speciale O (N * P) per un calcolo prima di fare qualsiasi attraversamento?

In quanto sopra, N è la dimensione dell'array, P è il numero di operazioni che hai eseguito sull'array?

Ogni operazione - un'inversione - spingerebbe in un altro array una coppia, rappresentando il primo e l'ultimo oggetto da scambiare.

Quindi, dato un array ABCDE

rappresenteremmo lo scambio BACDE come

(1,2)

Quindi potremmo rappresentare lo scambio su EDCAB (inversione completa) come

(1,5)

Tuttavia, non ci preoccuperemo di aggiornare l'array originale per il periodo di transizione, quindi possiamo rappresentare la sequenza di eventi come

[(1,2),(1,5)]

E poi uno scambio finale su EDACB come

(3,4)

per darci

[(1,2),(1,5),(3,4)]

Ovviamente finora abbiamo avuto solo operazioni O (1), perché ognuna è solo un inserimento di una tupla nel nostro array. O lista, o qualsiasi altra cosa.

Infine, per produrre l'EDACB otteniamo

[ABCDE] * [(1,2),(1,5),(3,4)]

Dove per ogni punto nell'array iniziale determiniamo la sua nuova posizione

Xnew = [(1,2),(1,5),(3,4)].Xorig

 = ( (3,4).( (1,5).( (1,2).Xorig)))

 Where each element of our array, the tuple (defined as (α,β), actions like so:

 Xnew = α-Xorig+β
    where  α>Xorig>β (that is, don't do anything if Xorig isn't in (α,β) )

Quindi questo richiederà (tutti gli elementi nel nostro set) * (numero di tuple di cui dobbiamo preoccuparci)

Tuttavia, dipenderete sempre dal numero di operazioni eseguite sull'array ...

Potrebbe esserci un modo per suddividere l'array in "bit", quindi per ogni elemento in N si applica un valore discreto ad esso (cioè se N < 2, +3, se N > = 2 & N < 5 -1, +3) ma al momento non so come lo faresti.

Tuttavia, quanto sopra sarà molto più semplice della scrittura di una nuova collezione, e per la piccola P altrettanto efficace.

    
risposta data 01.11.2013 - 18:11
fonte

Leggi altre domande sui tag