algoritmo eficiente para distribuir el trabajo?

Question

Es un poco complicado de explicar, pero aquí vamos. Básicamente, la cuestión es "¿Cómo romper problemas en subproblemas de una manera eficiente". "Eficiente" significa aquí, los subproblemas interrumpidas son tan grandes como sea posible. Básicamente, sería ideal si no tengo para romper los problemas en absoluto. Sin embargo, debido a que un trabajador sólo puede trabajar en bloques específicos de los problemas, que sí es necesario romper. Pero yo quiero encontrar una manera de hacer esto tan gruesa como sea posible.

Aquí hay un código de pseudo ..

Tenemos problemas como éste (lo siento es en Java. Si usted no entiende, yo estaría encantado de explicar).

class Problem {
    final Set<Integer> allSectionIds = { 1,2,4,6,7,8,10 };
    final Data data = //Some data
}

Y un subproblema es:

class SubProblem {
    final Set<Integer> targetedSectionIds;
    final Data data;

    SubProblem(Set<Integer> targetedSectionsIds, Data data){
        this.targetedSectionIds = targetedSectionIds;
        this.data = data;
    }
}

El trabajo se parecerá a esto, a continuación.

class Work implements Runnable {
    final Set<Section> subSections;
    final Data data;
    final Result result;

    Work(Set<Section> subSections, Data data) {
        this.sections = SubSections;
        this.data = data;
    }

    @Override
    public void run(){
        for(Section section : subSections){
            result.addUp(compute(data, section));
        }
    }
}

Ahora tenemos casos de 'trabajador', que tienen su propia sections I have estado.

class Worker implements ExecutorService {
    final Map<Integer,Section> sectionsIHave;
    {
        sectionsIHave = {1:section1, 5:section5, 8:section8 };
    }

    final ExecutorService executor = //some executor.

    @Override
    public void execute(SubProblem problem){
        Set<Section> sectionsNeeded = fetchSections(problem.targetedSectionIds);
        super.execute(new Work(sectionsNeeded, problem.data);
    }

}

uf.

Por lo tanto, tenemos una gran cantidad de Problems y Workers están constantemente pidiendo más SubProblems. Mi tarea es romper Problems en SubProblem y darle a ellos. La dificultad es, sin embargo, que tengo que, posteriormente, recoger todos los resultados de los subproblemas y de combinación (reducir) ellos en un Result para toda la Problem.

Esta es, sin embargo, costoso, por lo que quiero dar a los trabajadores "trozos" que son tan grandes como sea posible (tiene el mayor número posible targetedSections).

No tiene que ser perfecto (matemáticamente lo más eficiente posible o algo así). Es decir, yo supongo que es imposible tener una solución perfecta, porque no se puede predecir cuánto tiempo tomará cada cálculo, etc .. Pero no es una buena solución heurística para esto? O tal vez algunos recursos que puede leer hasta antes de entrar en el diseño?

Cualquier consejo es muy apreciada!

EDIT: Tenemos control sobre la asignación de la sección, también, para controlar esa es otra opciones. Básicamente, la única restricción sobre esto es que un trabajador sólo puede tener un número fijo de secciones.

Answer 1

De acuerdo, parece que usted tiene un modelo sharding para usted red de servicios, hacemos algo similar y se utiliza un índice inverso de "entityId" (sectionId) al "cliente" (trabajador) que se conectará a la red en particular servicio que va a hacer frente a esa entidad específica. método más simple (véase más adelante) es el uso de un mapa inversa de id para trabajador. Si la memoria es una limitación otra posibilidad es utilizar una función (por ejemplo sectionId número% de los servicios).

para dar los servicios tanto trabajo como sea posible, hay un algoritmo de procesamiento por lotes simple que va a llenar a lote en cierta máximo especificado por el usuario. Esto permitirá trozos de trabajo para ser de un tamaño más o menos de acuerdo a la rapidez con los servicios remotos son capaces de consumirlos.

public class Worker implements Runnable {

    private final Map<Integer, Section> sections;
    private final BlockingQueue<SubProblem> problemQ = new ArrayBlockingQueue<SubProblem>(4096);
    private final int batchSize;

    public Worker(final Map<Integer, Section> sectionsIHave, final int batchSize) {
        this.sections = sectionsIHave;
        this.batchSize = batchSize;
    }

    public Set<Integer> getSectionIds() {
        return sections.keySet();
    }

    public void execute(final SubProblem command) throws InterruptedException {

        if (sections.containsKey(command.getSectionId())) {
            problemQ.put(command);
        } else {
            throw new IllegalArgumentException("Invalid section id for worker: " + command.getSectionId());
        }

    }

    @Override
    public void run() {
        final List<SubProblem> batch = new ArrayList<SubProblem>(batchSize);
        while (!Thread.interrupted()) {
            batch.clear();

            try {
                batch.add(problemQ.take());
                for (int i = 1; i < batchSize; i++) {
                    final SubProblem problem = problemQ.poll();
                    if (problem != null) {
                        batch.add(problem);
                    } else {
                        break;
                    }

                    process(batch);
                }
            } catch (final InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    private void process(final List<SubProblem> batch) {
        // Submit to remote process.
    }

    private static Map<Integer, Worker> indexWorkers(final List<Worker> workers) {
        final Map<Integer, Worker> temp = new HashMap<Integer, Worker>();
        for (final Worker worker : workers) {
            for (final Integer sectionId : worker.getSectionIds()) {
                temp.put(sectionId, worker);
            }
        }
        return Collections.unmodifiableMap(temp);
    }

    public static void main(final String[] args) throws InterruptedException {
     // Load workers, where worker is bound to single remote service
        final List<Worker> workers = getWorkers();
        final Map<Integer, Worker> workerReverseIndex = indexWorkers(workers);
        final List<SubProblem> subProblems = getSubProblems();
        for (final SubProblem problem : subProblems) {
            final Worker w = workerReverseIndex.get(problem.getSectionId());
            w.execute(problem);
        }
    }
}