Java: эффективная концепция коллекции для парных объектов

Question

Мне не хватает какой-то функциональности сбора для конкретной проблемы.

Я хотел бы начать с нескольких сведений о предыстории проблемы - возможно, есть более элегантный способ ее решения, который не заканчивается конкретной проблемой, с которой я застрял:

Я моделирую объемную сетку из тетраэдрических ячеек (2D-аналогом будет треугольная сетка). Два тетраэдра считаются смежными, если они имеют одну треугольную грань (которая занимает три вершины). Мое приложение должно иметь возможность перемещаться от ячейки к ячейке через их общее лицо.

Чтобы удовлетворить некоторые другие требования, мне пришлось разделить грани на две так называемые полу-грани, которые имеют одинаковые вершины, но принадлежат разным ячейкам и имеют противоположную ориентацию.

Приложение должно иметь возможность совершать такие звонки (где Face моделирует половину лица):

Cell getAdjacentCell(Cell cell, int faceIndex) {
    Face face = cell.getFace(faceIndex);
    Face partnerFace = face.getPartner();
    if (partnerFace == null) return null; // no adjacent cell present
    Cell adjacentCell = partnerFace.getCell();
    return adjacentCell;
}

Реализация getPartner() -метода является рассматриваемым методом. Мой подход заключается в следующем:

Face -объекты могут создавать некий неизменный Signature -объект, содержащий только конфигурацию вершины, ориентацию (по часовой стрелке (по часовой стрелке) или против часовой стрелки (по часовой стрелке)) и обратную ссылку на исходную Face-объект. Face.Signature-объекты считаются равными (@Override equals()), если они занимают одни и те же три вершины - независимо от их ориентации и связанной с ними ячейки.

Я создал два набора в Mesh -объектах, чтобы они содержали все полупериоды, сгруппированные по их ориентации:

Set<Face.Signature> faceSignatureCcw = new HashSet<Face.Signature>();
Set<Face.Signature> faceSignatureCw = new HashSet<Face.Signature>();

Теперь я могу определить, существует ли партнер ...

class Face {
    public Face getPartner() {
        if (this.getSignature().isCcw()) {
            boolean partnerExists = this.getMesh().faceSignatureCw.contains(this);
        } else {
            boolean partnerExists = this.getMesh().faceSignatureCcw.contains(this);
        }
    }
}

... но Set не позволяет получить конкретный объект, который он содержит! Это просто подтверждает, что он содержит объект, который соответствует через .equals().

(конец фоновой информации)

Мне нужна Collection -концепция, которая обеспечивает следующие функциональные возможности:

• добавить Face -объект в коллекцию (дубликаты запрещены приложением и поэтому не могут возникать)
• получить партнера из коллекции для данного Face -объекта, который .equals(), но имеет противоположную ориентацию

Возможное (но способ замедлить) решение:

class PartnerCollection {
    List<Face.Signature> faceSignatureCcw = new ArrayList<Face.Signature>();
    List<Face.Signature> faceSignatureCw = new ArrayList<Face.Signature>();

    void add(Face.Signature faceSignature) {
        (faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw).add(faceSignature);
    }

    Face.Signature getPartner(Face.Signature faceSignature) {
        List<Face.Signature> partnerList = faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw;
        for (Face.Signature partnerSignature : partnerList) {
            if (faceSignature.equals(partnerSignature)) return partnerSignature;
        }
        return null;
    }
}

Для завершения. Конечное приложение должно обрабатывать сотни тысяч Face -объектов в режиме реального времени. Так что производительность это проблема.

Заранее спасибо всем, кто хотя бы пытался следовать за мной до этого момента :) Я надеюсь, что есть кто-то, у кого есть правильная идея, чтобы решить эту проблему.

Answer 1

Что-то не так с использованием двух Map<Face.Signature, Face.Signature>?
По одному на каждое направление?

Я бы так и сделал. Там практически нет кода для этого.

Answer 2

Рассматривали ли вы просто предоставление каждому лицу элемента данных партнера?Например,

public class Face
{
    Face partner;
    //whatever else
}

Конструкция Face.Signature немного волосатая и действительно не нужна.Если у каждого лица есть партнер (или достаточно Face объектов могут иметь партнера, то имеет смысл подумать, что между Face и партнером Face существует отношение has-a ),соединение должно быть просто переменной экземпляра.Если вы можете использовать этот подход, он должен значительно упростить ваш код.Если нет, опишите причину, по которой это не работает для вас, чтобы я мог продолжать пытаться помочь.

Answer 3

Здесь поздно ночью, и я не полностью подготовил ваш вопрос. Итак, я прошу прощения, если это не имеет никакого смысла, но рассматривали ли вы вопрос об использовании структуры данных графа? Если структура данных графа действительно является возможным решением, вы можете проверить jGraphT

Answer 4

Используя дизайн, который у вас есть сейчас, нет способа обойти что-то, что нужно перебрать где-то . Вопрос в том, где вы хотите, чтобы эта итерация происходила? Я предлагаю вам сделать это:

    List<Face.Signature> partnerList = faceSignature.isCcw() ? faceSignatureCw : faceSignatureCcw;
    int idx = partnerList.indexOf(faceSignature);
    if(idx == -1)
       return null;
    return partnerList.get(idx);

Кроме того, если вы используете Lists и знаете, что начальный размер должен быть довольно большим, вы могли бы также сказать, new ArrayList(100000) или около того.

Конечно, это не единственный метод, только тот, который гарантирует, что итерация будет оптимальной.

РЕДАКТИРОВАТЬ: После некоторых размышлений я считаю, что идеальной структурой данных для этого был бы Octuply Linked List, который может сделать вещи запутанными, но также очень быстрыми (сравнительно).