Trova la migliore sottocombinazione dalla combinazione data

Question

Trova la migliore sottocombinazione dalla combinazione data

#1 da (1 voti)
#2 da (0 voti)

3

Ogni componente ha più stati possibili e qualsiasi numero di essi può essere attivo alla volta. Alcune combinazioni di stati hanno un valore associato ad esso. In qualsiasi momento, vuole essere in grado di ottenere il miglior valore per gli stati attualmente attivi del componente. Il problema è quando non c'è un valore associato alla combinazione esatta, non riesco a pensare a un modo decente di implementare la ricerca del valore migliore che non sia orribilmente inefficiente. Lascia che te lo dimostri dal momento che potrei non averlo chiarito completamente.

Per un dato componente, ci sono stati possibili A-Z e valori possibili 0-9.

Stato corrente: [A,B,C]

Associazioni valore-stato:

[A,E]=5
[A]=1
[A,C]=3
[B,C]=9

Il valore corretto sarebbe 3 poiché ha il maggior numero di stati comuni e nessun stato non comune. Se due combinazioni di stati sono di uguale somiglianza, come [A, C] e [B, C], idealmente, verrà scelto il primo che verrà definito.

L'unica soluzione a cui potrei pensare è controllare ogni possibile combinazione che potrebbe diventare davvero inefficiente con un numero più elevato di stati.

Vale anche la pena notare che questo è simile alle pseudo classi nei CSS, anche se non sono riuscito a trovare alcuna informazione su come è implementato.

language-agnostic design java

posta Stripies 24.10.2016 - 17:05

fonte

2 risposte

Leggi altre domande sui tag language-agnostic design java

Problema produttore / consumatore con 2 mutex? Consigli di architettura per Android

score 1 · Answer 1

Possiamo prendere un trucco dalla ricerca del testo e creare un indice inverso dagli stati alle associazioni valore stato (SVA). La cosa bella di questo approccio è che quando cerchiamo il miglior SVA, dobbiamo solo controllare il nostro set di input una volta sola e non dobbiamo assolutamente guardare il contenuto degli SVA (li guardiamo solo nel indice). Al contrario, la versione ingenua deve confrontare l'input con i valori SVA per ogni SVA, che può essere molte volte più lavoro. Ecco una rapida implementazione in Python dell'idea:

class SVA:
    def __init__(self, states, value):
        """
        :type states: Iter
        :type value: int
        """
        self.states = frozenset(states)
        self.value = value

    def __len__(self):
        return len(self.states)

    def __iter__(self):
        return iter(self.states)

    def __hash__(self):
        return hash((self.states, self.value))


def index(svas):
    """
    Given a collection of SVAs return an dictionary from each value to the set of SVAs in it.
    """
    index = dict()

    for sva in svas:
        for value in sva:
            index.setdefault(value, set())
            index[value].add(sva)

    return index


class IndexedSVAs:
    def __init__(self, svas):
        """
        :type svas: iter(SVA)
        """
        self.svas = svas
        self._index = index(svas)
        self._sva_positions = dict((sva, i) for (i, sva) in enumerate(svas))

    def __getitem__(self, item):
        return self._index[item]

    def __iter__(self):
        return iter(self.svas)

    def position(self, sva):
        return self._sva_positions.get(sva, -1)


def find_best_fit(states, index):
    """
    Given the output of index and some values, find the SVA with the most values in common with the given and
    with none not in common.
    """
    sva_counter = dict((sva, 0) for sva in index)

    for state in states:
        for sva in index[state]:
            sva_counter[sva] += 1

    candidates = [sva for (sva, count) in sva_counter.items() if len(sva) <= count]
    return max(*candidates, key=lambda sva: (len(sva), -index.position(sva)))


svas = [SVA(['A', 'E'], 5), SVA(['A'], 1), SVA(['A', 'C'], 3), SVA(['B', 'C'], 9)]
indexed = IndexedSVAs(svas)
print(find_best_fit(['A', 'B', 'C'], indexed).value)

che stampa 3 come previsto.

score 0 · Answer 2

The only solution I could think of is checking every possible combination.

Non penso che ci sia molto altro da fare a causa di questo requisito:

there isn't a value associated with the exact combination

Se stavi cercando la combinazione esatta, potresti costruire un albero binario che potresti cercare più velocemente.

L'unica ottimizzazione che vedo per il tuo codice attuale è di tornare il prima possibile. Forse puoi fare ipotesi come, Ho [A,B,C] e so che la combinazione esatta non c'è, ora ho trovato [A,C] c'è la possibilità di trovare una corrispondenza migliore? per smettere di cercare ulteriormente . Tuttavia, non sono sicuro che ne troverai molti che sono spesso applicabili.

which would could get really inefficient with higher number of states

Solo un pensiero rapido: se gli stati sono binari e indipendenti, potresti rappresentarli a bit. Le operazioni binarie tendono ad essere veloci. Forse puoi trovare un modo in & 'nello stato corrente con le associazioni conosciute e poi contare i bit del risultato o qualcosa del genere.