Java：高效的配對對象集合概念

我想先從這個問題的背景幾個信息 - 也許有解決它更優雅的方式，這並不在具體的問題最終我堅持用：

我m建模由四面體單元構成的體積網格（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 - 對象可以創建某種不可變的對象 - 僅包含頂點配置，方向（順時針（cw）或逆時針（ccw））和反向引用到原始的人臉對象。如果Face.Signature對象佔據相同的三個頂點，則認爲它們是相同的（@Override equals()） - 無論它們的方向及其關聯的單元格如何。

我創建了兩個臺在Mesh -objects包含通過定向分組的所有半面：

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 -concept其提供了以下功能：

添加Face -object到Collection（複製是由應用程序被禁止和因此不會發生）
從集合中檢索給定的合作伙伴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 -Objects的實時環境。所以表現是的一個問題。

在此先感謝任何人至少試圖跟隨我到這一點:) 我希望有任何人有正確的想法來解決這個問題。

來源

2011-07-22 Kai Giebeler

使用兩個Map<Face.Signature, Face.Signature>有什麼不對？
每個方向一個？

這就是我要做的。幾乎沒有代碼。

來源

2011-07-22 23:46:50 Bohemian

由於'Map'的關鍵部分是一個'Set'，我豈不落得同樣的問題與我的'Set'的解決方案？我將能夠認識到存在一個夥伴對象，但我無法獲取該對象本身。或者我錯過了什麼？ –

...其實我錯過了一些東西 - 你是對的。我應該能夠使用條目的值檢索所需的對象。它仍然是某種內存浪費，但它應該解決原來的問題。我會試一試，謝謝！ –

使用你現在的設計，沒有辦法需要迭代某處。問題是，你想在哪裏發生迭代？我建議你這樣做：

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鏈表，它可以使事情混亂，但也非常快（相對）。

來源

2011-07-22 23:38:18 MirroredFate

它這裏的深夜，我還沒有準備好你的問題完全。所以，如果這沒有任何意義，我表示歉意，但是您是否考慮過使用圖形數據結構？如果圖形數據結構確實是一種可能的解決方案，那麼您可能需要查看jGraphT

來源

2011-07-22 23:43:00

你有沒有考慮只是給每個面的合作伙伴數據成員？如，

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

的Face.Signature結構是有點毛茸茸的，真的不應該需要。如果每個人臉上有一個合夥人（或足夠Face對象可以有一個合作伙伴，它是有道理的認爲有一個有-一個一個Face和合作夥伴Face之間的關係），連接應該僅僅是一個實例變量。如果你可以使用這種方法，它應該大大簡化你的代碼。如果不是，請回復這個不適合你的原因，這樣我就可以繼續嘗試幫助。

來源

2011-07-23 03:42:51 Gravity

這只是一個設計決定。 Signature允許我定義與我將用於「Face」類本身的不同類型的等式。如果解決方案不需要重寫'equals（）'或'hashCode（）'，我可能會回退到單個實例變量。但是，還有一些其他應用程序特定的原因表明您無法意識到的「Signature」級別，因爲我沒有提及它們。但是，切換到實例變量本身並不能解決問題。 –

Java：高效的配對對象集合概念

回答

相關問題