醫學資訊學/計算機化病歷案例研究
< 醫學資訊學
在澳大利亞，廣泛引入基於 PC 的計算機病歷系統（主要基於 Windows 作業系統）之前，普通科醫生診所的病歷記錄使用的是 RACGP 標準病歷表格，用於患者登記和摘要，以及病程記錄。
使用計算機化病歷系統帶來了許多優勢，例如提高了處方可讀性，從而理論上減少了由於 GP 手寫處方到藥劑師之間溝通不暢導致的用藥錯誤，也消除了藥劑師需要打電話給 GP 確認難以辨認處方的業務效率低下問題。隨著整合地址簿和文字處理功能的加入，醫生可以更快地轉診至專家。醫學上的理由是，專家也可以自動獲取患者病症和處方藥物的摘要列表，並將其包含在列印的轉診信中，從而改善了患者交接過程，但這種方法很少被依賴，除了可能由外科醫生使用。
澳大利亞的病歷系統還可以下載病理學和放射學報告，通常透過病理學服務提供商的外部專有下載客戶端進行，該客戶端將結果檔案放置在檔案目錄中，供 GP 病歷系統解析，使用一些簡單的行定向格式，例如 PIT。這發生在網際網路接入從撥號接入發展到 ADSL/有線接入，實現持續接入，並需要使用加密和身份驗證網際網路標準開發安全網際網路傳輸的背景下。
在澳大利亞背景下，早期採用某家供應商的解決方案意味著，用於儲存小型企業記錄的資料庫技術在十多年內保持相當穩定，實際上，DBase/Foxpro 的 DBF 檔案格式成為許多年的大多數普通科醫生電子病歷的基礎。
由於普通科醫生診所規模大多是小規模的，因此沒有必要改變更簡單但更優雅的 DBASE 格式資料庫技術，Windows 網路檔案系統的機會性檔案鎖定足以滿足系統使用需求，即使在有多名醫生的診所中，十多個使用者同時訪問也是如此。基於 B 樹的 DBASE 索引檔案提供了可擴充套件性，因為記錄會累積多年的患者病程記錄、操作、疫苗接種、轉診、掃描的回覆信件以及下載的文字結果。但 DBASE 索引檔案的結構沒有公開文件，並且在沒有詳細瞭解 DBASE IDX/MDX 檔案的情況下，快速查詢給定患者的所有相關記錄的能力是 GP 基於計算機的病歷功能定製的主要障礙。
在一段時間內，這意味著任何普通科醫生都能夠在知識儲備範圍內成為自己病歷系統的掌控者，因為 DBF 檔案格式眾所周知，它是一種邏輯堆檔案格式，記錄只是簡單地追加到儲存特定表資訊的檔案末尾。但是，缺乏容易獲得/理解的有關 DBASE *索引*檔案結構的資訊構成了一個主要障礙。
本案例研究將嘗試說明 DBASE 的簡單、邏輯、透明的組織如何與對一種特定計算機演算法（即線性雜湊）的基本理解相交，並提供擴充套件功能的手段。隨著向供應商特定實現的 SQL 資料庫系統的遷移，這個時代令人遺憾地結束了，未來的防護和免受供應商市場撤出影響變得更加困難。
現代資料庫系統通常使用 SQL 宣告式程式設計介面作為前端，因為 SQL 對非程式設計師來說相對容易學習，但需要大量的基礎設施來支援它，並且在 SQL 語法和用於檢索的底層檔案格式和演算法之間存在很大距離。大多數資料庫系統仍然依賴索引來指示給定記錄的鍵值儲存在何處，索引中使用的演算法要麼基於 B 樹的變體，要麼基於雜湊。B 樹索引的主要優勢在於索引鍵按排序方式儲存，因此可以根據較低的鍵值或較高的鍵值檢索一系列記錄。例如，所有患者姓氏以 Smi 開頭的記錄都可以透過使用 Smia 到 Smiz 作為上下限值來檢索。
雜湊演算法主要在索引中使用，因為它們速度相對較快。簡單來說，猴子爬樹枝找到香蕉所需的時間比猴子閱讀指向香蕉的指示牌所需的時間更長。因此，雜湊索引在實現 *JOIN* 操作時通常更快。例如，患者的病歷可能包含人口統計表中的條目，透過 ID 欄位引用，該欄位稱為主鍵。患者的藥物可能儲存在藥物表中，該表也有一個 DEMOGRAPHIC_ID 欄位，稱為外部索引鍵欄位，因此，透過對人口統計表和藥物表進行聯接，我們可以透過識別具有 ID 值的患者來識別患者正在服用的藥物。
什麼是雜湊？雜湊是將一些資料值轉換為整數的過程。通常，一個好的雜湊函式會為要轉換的資料值域生成一個大致隨機的整數。需要一個好的雜湊函式的原因是，生成的雜湊值用作索引到儲存位置，在這個上下文中，就是索引雜湊檔案中的檔案位置。因此，為了有效地使用空間，從輸入資料集中派生的所有可能的雜湊值應該在儲存地址範圍內大致均勻分佈。
另一個有用的概念是衝突，即兩個不同的值被雜湊到同一個雜湊整數。為了處理衝突，可以在每個位置分配額外的空間，這樣就有了固定數量的額外位置，這可以稱為一個桶（槽）。如果雜湊到一個位置的鍵數量超過了桶中的槽數，該怎麼辦？那麼可以由該桶引用另一個桶，這稱為溢位桶/塊/空間。
由於普通科醫生資料庫的規模較小，因此可以認為標準雜湊演算法可以用於實現外部索引檔案，使用非常大的索引檔案空間，每個可能的雜湊值對應一個桶，如果需要，可以將溢位桶追加到索引檔案的末尾。
更優雅的演算法是線性雜湊演算法，它在幾乎所有優秀的資料庫基礎教程中都有提及，與可擴充套件雜湊並列，被認為是資料庫系統中使用的大型基於檔案索引需求的最佳雜湊演算法。
基於檔案的索引的主要限制是檔案本身的性質：它們很容易建立，也很容易追加，但在檔案中間插入資料塊很昂貴，因為在插入點，插入點之後的檔案的剩餘部分必須複製到一個臨時檔案，原始檔案在插入點截斷，新的塊追加到截斷的檔案，然後將臨時檔案的內容追加到該檔案。B 樹一次擴充套件一個節點/塊，新的節點可以追加到檔案末尾。可擴充套件/線性雜湊也可以一次擴充套件一個塊，儘管可擴充套件雜湊可能需要在索引檔案開頭預留一個目錄結構的最大尺寸估計，或者使用單獨的目錄檔案，因為目錄結構會定期加倍。
B 樹索引使用一種演算法，其中鍵與指向檔案地址的指標相關聯，該地址標記表示 B 樹中其他節點的其他檔案資料塊的開始。B 樹是自平衡的，因為條目的溢位意味著一個節點被拆分，並且一個額外的鍵被傳遞到父節點，從而減緩了樹高度的增長；最終導致根節點被拆分。新的節點只是簡單地追加到索引檔案的末尾，並且檔案偏移值（節點“指標”）允許隨機檔案訪問從根節點向下遍歷塊。
可擴充套件雜湊和線性雜湊類似於基數搜尋，因為地址空間透過增加雜湊值中使用的位數來增加，每增加一位就會使地址空間加倍。維基百科的百科全書參考資料對可擴充套件雜湊和線性雜湊進行了充分的描述。
然而，由於下面的程式碼中使用了線性雜湊，因此需要簡要回顧一下：線性雜湊透過使用一個條件雜湊函式來實現，該函式依賴於一個迭代變數 split。在 split 值的第一次迭代中，該變數的範圍從雜湊值 0 到 N-1，即第一次迭代的初始桶數。條件雜湊函式的工作原理如下。
h' = h mod M where M = N x 2 ^ level, if h' < split, then h' = h mod M' where M = N x 2 ^(level +1).
每當任何一個桶溢位時，都需要更多空間，這可以透過臨時建立一個附加到溢位桶的溢位桶來處理。但它也透過將一個桶附加到當前的桶列表中來處理，因此當 split 變數為零時，附加的桶在 N 中。完成此操作後，split 變數將遞增：此後，條件雜湊函式將使用 mod 2N 而不是 N 來計算任何最初雜湊為零的值，以便記錄將被雜湊到 0 或 N。例如，如果 y = x mod R 且 y' = x mod 2R，則對於任何非負整數 x，y' = y 或 y' = y + R。這方便地將 split 遍歷的值雜湊到原始編號的桶 n 或另一個編號的桶，該桶為 n + N 乘以 2 ^ level。這就是線性雜湊，因為桶的數量呈線性增長。每當 split 變數達到 N * 2 ^ level（或 N 左移 level 次）時，level 將遞增，而 split 將重置為 0，以便條件雜湊函式可以訪問下一級新增的桶，同時在所有可用桶上進行迴圈訪問，在它們積累太多記錄之前將它們拆分，例如：對於 0 到 N-1，N 到 2N-1 是可訪問的；對於 0 到 2N-1，2N 到 4N-1 是可訪問的，等等。
案例研究賬戶：過敏症檢查器，以及基於作業系統目錄的諮詢檔案日誌
[edit | edit source]在本案例研究中，最初的“癢到抓撓”是一個使用者需求，要求對使用者輸入的過敏症資訊進行監控，因為雖然醫生在開藥前幾乎會自動詢問是否存在過敏症，但澳大利亞的一般做法是要求在所有患者身上記錄過敏症，無論每次就診時是否檢查過敏症列表的有效性。這導致實現了一個用 java 編寫的外部程式來檢查與過敏症相關的 DBF 表格，最初發現記憶體中的 Map 類（HashMap、TreeMap）足以在程式啟動時索引這些表格，並維護一個臨時的記憶體索引以方便查詢。透過輪詢作業系統“登錄檔”中與程式相關聯的屬性來找到一種方法，以便在開啟患者記錄時檢測到，以便觸發對過敏症表格的查詢，如果尚未記錄過敏症，則會彈出一個提醒視窗，並且此檢查將使用 java Timer 類定期執行。
下一個使用者需求是記錄諮詢統計資訊，以幫助審查之前的諮詢，以便臨床醫生可以根據醫療記錄程式未提供的其他詳細資訊，在他需要的情況下審查他的實踐並輕鬆找到他最近見過的患者。這需要在一個大小超過記憶體中的 Map java 類能力的表格中進行查詢，因此建議使用線性雜湊實現來可擴充套件地索引此類表格。
不幸的是，最初的實現將塊管理作為檔案實體混合在一起，無法正常工作，而且難以除錯，因此第二個實現集中於首先證明演算法在記憶體中是有效的。
一旦錯誤被消除（主要是由於 java 語言固有的無符號整數表示導致動態雜湊函數出現錯誤），記憶體中的線性雜湊實現被用作基於檔案的塊管理器的快取結構。塊基本上被儲存為一個檔案，檔名與塊號相同。
由於 java 的內建 LinkedList 型別能夠在給定索引位置儲存空值，因此空值被用作快取未命中標誌，要求檔案塊管理器載入一個塊。
每當載入一個塊時，也會透過比較執行時的空閒記憶體與塊列表大小乘以平均塊大小來進行檢查，如果它低於此值的某個倍數，則透過遍歷列表並將其寫入磁碟來選擇一些非空塊。一旦塊被寫入，塊中的資料就會透過清除對它們的任何引用（例如，呼叫 map.clear()）並隨後呼叫垃圾收集器（System.gc()）來使垃圾收集器可以使用。這將導致可用於資料物件分配的可用 java 記憶體增加。
由於塊的載入和儲存已經適用於快取，因此發現它們可以用於載入先前建立的線性雜湊結構，或儲存新構建的結構。這也需要因為從大量記錄構建一個持久索引結構需要超過 10 分鐘的時間，對於這樣一個監控程式來說，這是不可接受的啟動時間。
下面是 Map 介面外掛，以及一個帶有用於儲存和載入索引的靜態公共方法的檔案管理器類。它說明了從對演算法的基本理解出發，這可以用來提供基於計算機的醫療記錄系統的透明性和可擴充套件性。這不會提供 DBF 檔案訪問邏輯，但這可以透過使用容易獲得的 DBF 檔案結構和基本型別的描述來實現，這些類可以作為 java 關聯陣列 Map 類的直接插入，作為資料庫索引的程式表示，這些索引可以透過遍歷儲存在 DBF 表格檔案中的記錄列表來構建。一旦索引被構建並儲存到磁碟，它可以在將來啟動監控程式時重新載入。在使用任何索引之前，可以將索引中的條目數量與 DBF 表格檔案頭中記錄的當前記錄數量進行比較，如果更少，則可以從位置 L（最後一個記錄數量）讀取記錄到 N（當前記錄數量），並將它們新增到索引物件中。因此，一旦索引被構建，它就會定期更新，透過檢查檔案中的先前記錄數量，該數量在每次將索引儲存到磁碟時儲存為磁碟上的索引頭的一部分。使用一個關閉鉤子來確保在正常關閉時更新索引。
線性雜湊對映實現的具體用途是建立以患者身份鍵為中心的進度條目索引。每個與給定患者相關的進度記錄列表都作為與患者 ID 作為鍵的連結列表物件儲存。然後將患者 ID 透過動態雜湊函式傳遞，並將患者 ID 到連結列表進度 ID 的鍵值對儲存為有限大小的塊物件的條目。鑑於此表示，讀者可以推斷出桶的大小不是可變的，或者使用了大量浪費的空間來適應最大值列表大小。由於塊的大小可變，因此決定每個塊都是一個檔案，並且整個檔案系統目錄將用於儲存線性對映的資料。這將在處理塊時增加開啟/關閉檔案的核心開銷，因此，由於將塊表示為單個檔案的簡化決策，而不是將固定大小的塊附加到單個索引檔案中，因此實現可能速度更慢。然而，當使用完全構建的索引檢索特定患者的記錄以記錄諮詢審查資訊時，效能足夠快。
這種使用線性雜湊對映構建索引以連線/關聯表格的使用者 API 將 SQL 連線查詢的隱藏複雜性與表格模式的顯式審查相交換，以換取學習 java 語言的 arguably 相同的複雜性，以及使用 java 語言的靈活性來輸出自定義報告。似乎沒有障礙可以簡單地將用於不同語言的方法翻譯過來，例如 python。
這種簡單的資料庫索引實現缺少什麼？ ACID 是一個購物清單首字母縮略詞，它會讓人想起；原子性、隔離性、一致性和永續性，在面對併發訪問和操作過程中的隨機系統崩潰時。到目前為止，對於作為本地過敏症檢查器和諮詢統計記錄器在單使用者機器上的使用，在 3 個月的使用時間內似乎沒有問題，但桌上型電腦從未在索引檔案映像更新過程中出現故障，這很少見，但由於沒有特別考慮，因此可能需要刪除索引檔案，並且在下次作業系統啟動時需要長時間的重新初始化索引（程式透過正在使用的 windows 作業系統的啟動選單執行）。
處理併發性的最簡單方法是使用 java 的 Collections.syncrhonizedMap 包裝器包裝 Map 介面，而處理可恢復性的標準方法是使用檢查點的預寫日誌。一些 DBMS 使用寫時複製，並保留先前寫入的資料值的版本，但什麼才是最小的足以滿足需求？主要的寫入操作是對現有鍵值對的值進行覆蓋，插入新的鍵值對，以及拆分塊。一種恢復方案稱為影子頁面，其中在檢查點保留頁面目錄/塊列表的副本，併為寫入儲存的塊賦予版本號，因此塊 x 將具有名稱“x.v”。這可以透過新增一個可序列化的小型對映屬性來實現，該屬性將塊號對映到塊。版本檔名。如果在上次檢查點之後發生崩潰，則影子塊列表和塊名稱對映將成為當前塊列表和名稱對映。如果需要，可以透過刪除任何名稱包含比當前影子塊名稱對映早的版本號的檔案來定期執行垃圾回收。
使用線性雜湊演算法實現的基本持久資料庫索引的 java 實現
[edit | edit source]package linearhashmap;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
/**
*
* @author S.Tan
*
* @param <K>
* key type , must implement equals() and hashCode()
* @param <V>
* value type
*
*
*/
public class LHMap2<K, V> implements Map<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 3095071852466632996L;
/**
*
*/
public static interface BlockListener<K, V> {
public void blockRequested(int block, LHMap2<K, V> map);
}
List<BlockListener<K, V>> listeners = new ArrayList<BlockListener<K, V>>();
// int savedBlocks;
int N;
int level = 0;
int split = 0;
int blockSize;
long totalWrites = 0;
List<Block<K, V>> blockList = new ArrayList<Block<K, V>>();
public void addBlockListener(BlockListener<K, V> listener) {
listeners.add(listener);
}
void notifyBlockRequested(int block) {
for (BlockListener<K, V> l : listeners) {
l.blockRequested(block, this);
}
}
public LHMap2(int blockSize, int nStartingBlocks) {
this.blockSize = blockSize;
this.N = nStartingBlocks;
for (int i = 0; i < nStartingBlocks; ++i) {
addBlock();
}
Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
@Override
public void run() {
showStructure();
}
}));
}
public static class Block<K, V> implements Externalizable {
/**
*
*/
int j = 0;
Block<K, V> overflow = null;
LinkedList<K> keyList = new LinkedList<K>();
LinkedList<V> valueList = new LinkedList<V>();
transient private LHMap2<K, V> owner;
transient private Map<K, V> shadow = new TreeMap<K, V>();
private boolean changed = false;
private int size = 0;
public LHMap2<K, V> getOwner() {
return owner;
}
public void setOwner(LHMap2<K, V> owner) {
this.owner = owner;
Block<K, V> ov = overflow;
while (ov != null) {
overflow.setOwner(owner);
ov = ov.overflow;
}
}
public Block() {
}
public Block(LHMap2<K, V> map) {
setOwner(map);
}
public V put(K k, V v) {
setChanged(true);
V v2 = replace(k, v);
if (v2 == null) {
++size;
if (keyList.size() == getOwner().blockSize) {
if (overflow == null) {
getOwner().blockOverflowed(this, k, v);
} else {
overflow.put(k, v);
}
} else {
keyList.addFirst(k);
valueList.addFirst(v);
}
}
return v2;
}
void setChanged(boolean b) {
changed = b;
}
public Map<K, V> drainToMap(Map<K, V> map) {
while (!keyList.isEmpty()) {
K k = keyList.removeLast();
V v = valueList.removeLast();
map.put(k, v);
}
if (overflow != null)
map = overflow.drainToMap(map);
garbageCollectionOverflow();
return map;
}
public void updateMap(Map<K, V> map) {
Iterator<K> ik = keyList.descendingIterator();
Iterator<V> iv = valueList.descendingIterator();
while (ik.hasNext() && iv.hasNext()) {
map.put(ik.next(), iv.next());
}
if (overflow != null)
overflow.updateMap(map);
}
private void garbageCollectionOverflow() {
if (overflow != null) {
overflow.garbageCollectionOverflow();
overflow = null;
}
}
public void addOverflowBucket() {
// assert overflow is needed
if (keyList.size() < getOwner().blockSize)
return;
if (overflow == null) {
overflow = new Block<K, V>(getOwner());
} else {
overflow.addOverflowBucket();
}
}
public V replace(Object key, V v2) {
if (overflow != null) {
V v = overflow.replace(key, v2);
if (v != null)
return v;
}
int j = 0;
for (K k : keyList) {
if (key.equals(k)) {
V v = valueList.get(j);
if (v2 != null) {
valueList.set(j, v2);
}
return v;
}
++j;
}
return null;
}
public boolean isChanged() {
return changed;
}
@Override
public void readExternal(ObjectInput arg0) throws IOException,
ClassNotFoundException {
int sz = arg0.readInt();
for (int i = 0; i < sz; ++i) {
K k = (K) arg0.readObject();
V v = (V) arg0.readObject();
shadow.put(k, v);
}
}
public void loadFromShadow(LHMap2<K, V> owner) {
setOwner(owner);
Block<K, V> b = this;
for (Map.Entry<K, V> entry : shadow.entrySet()) {
if (b.keyList.size() == owner.blockSize) {
Block<K, V> overflow = new Block<K, V>(owner);
b.overflow = overflow;
b = overflow;
}
b.keyList.add(entry.getKey());
b.valueList.add(entry.getValue());
}
shadow.clear();
}
@Override
public void writeExternal(ObjectOutput arg0) throws IOException {
if (!changed)
return;
Map<K, V> map = new TreeMap<K, V>();
// this is destructive of the block
updateMap(map);
int sz = map.size();
arg0.writeInt(sz);
for (Map.Entry<K, V> entry : map.entrySet()) {
arg0.writeObject(entry.getKey());
arg0.writeObject(entry.getValue());
}
setChanged(false);
}
}
void init() {
for (int i = 0; i < N; ++i) {
addBlock();
}
}
/**
* @param hashValue
* @return a bucket number.
*/
int getDynamicHash(int hashValue) {
long unsignedHash = (long) hashValue & 0xffffffffL;
int h = (int) (unsignedHash % (N << level));
// System.err.println("h = " + h);
if (h < split) {
h = (int) (unsignedHash % (N << (level + 1)));
// System.err.println("h < split, new h = " + h);
}
return h;
}
public V put(K k, V v) {
++totalWrites;
int h = getDynamicHash(k.hashCode());
Block<K, V> b = getBlock(h);
b.put(k, v);
return v;
}
public long getTotalWrites() {
return totalWrites;
}
private Block<K, V> getBlock(int h) {
notifyBlockRequested(h);
return blockList.get(h);
}
void blockOverflowed(Block<K, V> b, K k, V v) {
splitNextBucket();
b.addOverflowBucket();
b.put(k, v);
}
private void splitNextBucket() {
Block<K, V> b = getBlock(split);
TreeMap<K, V> map = new TreeMap<K, V>();
b.drainToMap(map);
addBlock();
System.err.printf("split N LEVEL %d %d %d \n", split, N, level);
if (++split >= (N << level)) {
++level;
split = 0;
}
for (Map.Entry<K, V> entry : map.entrySet()) {
K k = entry.getKey();
V v = entry.getValue();
int h = getDynamicHash(k.hashCode());
System.err.println(h + " ");
Block<K, V> b2 = getBlock(h);
b2.put(k, v);
}
}
private Block<K, V> addBlock() {
Block<K, V> b = new Block<K, V>(this);
blockList.add(b);
return b;
}
@Override
public void clear() {
blockList = new ArrayList<Block<K, V>>();
split = 0;
level = 0;
totalWrites = 0;// savedBlocks = 0;
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
return values().contains(value);
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new TreeSet<Map.Entry<K, V>>();
for (final K k : keySet()) {
set.add(new Entry<K, V>() {
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return get(k);
}
@Override
public V setValue(V value) {
return put(k, value);
}
});
}
return Collections.unmodifiableSet(set);
}
@Override
public V get(Object key) {
int h = getDynamicHash(key.hashCode());
Block<K, V> b = getBlock(h);
return b.replace(key, null);
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public Set<K> keySet() {
Set<K> kk = new TreeSet<K>();
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
kk.addAll(b.keyList);
Block<K, V> ov = b.overflow;
while (ov != null) {
kk.addAll(ov.keyList);
ov = ov.overflow;
}
}
return Collections.unmodifiableSet(kk);
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public V remove(Object key) {
return null;
}
@Override
public int size() {
return (int) Math.min(longSize(), (long) Integer.MAX_VALUE);
}
public long longSize() {
long sz = 0;
for (Block<K, V> b : blockList) {
Block<K, V> b1 = b;
while (b1 != null) {
sz += b1.size;
b1 = b.overflow;
}
}
return sz;
}
@Override
public Collection<V> values() {
List<V> list = new ArrayList<V>();
for (K k : keySet()) {
list.add(get(k));
}
return Collections.unmodifiableList(list);
}
private void showStructure() {
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
Block<K, V> ov = b.overflow;
int k = 0;
while (ov != null) {
ov = ov.overflow;
++k;
}
System.out.println("Block " + i + " size " + b.keyList.size()
+ " overflow blocks = " + k);
}
}
}
package linearhashmap;
import java.io.File;
import java.io.Serializable;
import java.util.List;
import java.util.Random;
public class LHMap2BlockFileManagerData implements Serializable{
/**
*
*/
private static final long serialVersionUID = 1L;
public byte[] buf;
public Random r;
public File baseDir;
public File home;
public int maxBlocks;
public int retired;
public double unloadRatio;
public List<Integer> retirees;
public int avgBlockSize;
public long avgCount;
public LHMap2BlockFileManagerData(byte[] buf, Random r, int retired,
List<Integer> retirees, long avgCount) {
this.buf = buf;
this.r = r;
this.retired = retired;
this.retirees = retirees;
this.avgCount = avgCount;
}
}
package linearhashmap;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Random;
/**
* This class manages the LHMap2 class block disk swapping, and saves and load
* an instance of the LHMap2 class. It has been used to externally index a
* legacy file based database of 100,000 record master table, and 1,000,000
* record sized child tables, and accounts for heap space available in the java
* virtual machine, so that OutOfMemory errors are avoided when the heap space
* is low by putting blocks back on files, and garbage collecting them. The main
* performance bottleneck appeared when loading a million record table for an
* index , on initial creation of the index.
*
* @author doctor
*
* @param <K>
* @param <V>
*/
public class LHMap2BlockFileManager<K, V> implements
LHMap2.BlockListener<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 2615265603397988894L;
LHMap2BlockFileManagerData data = new LHMap2BlockFileManagerData(
new byte[10000], new Random(), 0, new ArrayList<Integer>(), 0);
public LHMap2BlockFileManager(File baseDir, String name, int maxBlocks,
double unloadRatio) {
data.home = new File(baseDir, name);
if (!data.home.exists())
data.home.mkdir();
this.data.maxBlocks = maxBlocks;
this.data.unloadRatio = unloadRatio;
}
@Override
public void blockRequested(int block, LHMap2<K, V> map) {
LHMap2.Block<K, V> b = map.blockList.get(block);
if (b == null) {
int tries = 3; // for some reason, the File constructor can be
// asynchronous occasionally, so need to try again
// after delay
File f = new File(data.home, Integer.toString(block));
do {
if (f.exists())
break;
if (!f.exists()) {
if (--tries >= 0)
fatal(block);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
} while (true);
try {
ByteArrayInputStream bis = new ByteArrayInputStream(data.buf);
FileInputStream fis = new FileInputStream(f);
int sz = fis.read(data.buf);
fis.close();
addByteStats(sz);
ObjectInputStream ois = new ObjectInputStream(bis);
b = new LHMap2.Block<K, V>();
b.readExternal(ois);
ois.close();
b.loadFromShadow(map);
map.blockList.set(block, b);
--data.retired;
} catch (FileNotFoundException e) {
e.printStackTrace();
fatal(block);
} catch (IOException e) {
e.printStackTrace();
fatal(block);
} catch (ClassNotFoundException e) {
e.printStackTrace();
fatal(block);
}
}
int size = map.blockList.size();
try {
long freeMemory = Runtime.getRuntime().freeMemory();
long limitMemory = (long) (data.avgBlockSize * data.unloadRatio * size);
if (block % 30 == 0)
System.err.println("free memory =" + freeMemory + " limit "
+ limitMemory);
if (map.split % 20 == 19) {
// this is just to add statistics before really needing to
// retire
retireActiveBlock(map, block);
++data.retired;
} else if (freeMemory < limitMemory) {
for (int i = 0; i < map.blockList.size() / 4; ++i) {
retireActiveBlock(map, block);
++data.retired;
}
System.runFinalization();
System.gc();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
private void addByteStats(int sz) {
++data.avgCount;
data.avgBlockSize = (int) ((data.avgBlockSize * (data.avgCount - 1) + sz) / data.avgCount);
}
public void retireActiveBlock(LHMap2<K, V> map, int notThisOne)
throws FileNotFoundException, IOException {
int pick = 0;
int size = map.blockList.size();
for (pick = 0; pick < size
&& (pick == notThisOne || map.blockList.get(pick) == null); ++pick)
;
if (pick < size)
retireBlock(map, pick);
}
private void retireBlock(LHMap2<K, V> map, int pick) throws IOException,
FileNotFoundException {
LHMap2.Block<K, V> b = map.blockList.get(pick);
if (b == null)
return;
if (b.isChanged()) {
File f = new File(data.home, Integer.toString(pick));
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(bos);
b.writeExternal(oos);
oos.flush();
oos.close();
FileOutputStream fos = new FileOutputStream(f);
byte[] bb = bos.toByteArray();
fos.write(bb);
fos.flush();
fos.close();
if (bb.length > data.buf.length) {
data.buf = bb;
}
}
map.blockList.set(pick, null);
}
private void fatal(int block) {
Exception e = new Exception();
try {
throw e;
} catch (Exception e2) {
e2.printStackTrace();
}
System.err.println("block " + block
+ " requested and it is not in blocklist and not a file");
for (int i : data.retirees) {
System.err.print(i + " ");
}
System.err.println(" were retired");
System.exit(-2);
}
public static boolean metaExists(File indexDir, String name) {
File home = new File(indexDir, name);
return new File(home, "LinearMap2").exists();
}
public static <K, V> LHMap2<K, V> load(File baseDir, String name)
throws FileNotFoundException, IOException, ClassNotFoundException {
File home = new File(baseDir, name);
File f2 = new File(home, "LinearMap2");
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(f2));
LHMap2<K, V> map = (LHMap2<K, V>) ois.readObject();
ois.close();
loadBlocks(map);
return map;
}
private static <K, V> void loadBlocks(LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(map);
int size = map.blockList.size();
for (int i = 0; i < size; ++i) {
mgr.blockRequested(i, map);
}
}
public static <K, V> LHMap2BlockFileManager<K, V> getBlockManagerListener(
LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = (LHMap2BlockFileManager<K, V>) map.listeners
.get(0);
return mgr;
}
public static void save(File indexDir, String name,
LHMap2<?, ?> offsetMap) throws FileNotFoundException, IOException {
retireAllBlocks(offsetMap);
File home = new File(indexDir, name);
File f2 = new File(home, "LinearMap2");
ObjectOutputStream oos = new ObjectOutputStream(
new FileOutputStream(f2));
oos.writeObject(offsetMap);
oos.close();
}
private static <K, V> void retireAllBlocks(LHMap2<K, V> offsetMap)
throws FileNotFoundException, IOException {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(offsetMap);
int sz = offsetMap.blockList.size();
for (int i = 0; i < sz; ++i) {
LHMap2.Block<K, V> b = offsetMap.blockList.get(i);
if (b != null) {
mgr.retireBlock(offsetMap, i);
}
}
}
}
線性雜湊是一種雜湊演算法，對於基於鍵的連線非常有效，其中需要鍵之間的相等性。但是，需要範圍搜尋索引來回答某些查詢，例如以 SM 開頭的名字（以 SMZ 結尾）以查詢所有 SMITH，查詢所有超過 50 歲的糖尿病患者，查詢過去 12 個月內由 Z 醫生看過的所有超過 50 歲的患者，他們沒有進行血糖測試等等。
該演算法通常是 B 樹，並且在 1980 年代流行的資料庫中也是如此，例如 DBase 系列（foxpro、paradox 等），以及更新的流行資料庫，例如 Postgresql、Firebird、DerbyDb 等。B 樹是在 1960 年代後期作為一種索引演算法引入的，當需要範圍可搜尋索引時，似乎沒有更好的演算法（在實施方面如所實踐的那樣），據說如果需要在雜湊和 B 樹之間進行選擇，那麼後者提供了超集功能，但代價是損失 O(0-2) 磁碟訪問時間。
線性雜湊更容易理解，並且更容易對映到磁碟儲存，但 B 樹在概念上也同樣易於理解，只是除錯稍微困難一點。
B 樹的重要特徵是什麼？它基本上就像一棵二叉樹，實際上，一棵二叉樹實際上是一棵 B 樹，其中一個節點只有一個條目，而一個 B 樹節點可能包含 n 個條目，其中 n 大約在 10-100 之間，並且通常被引用為 n x（條目大小）= 物理磁碟塊大小的大小。這個想法是將一個塊載入到記憶體中並搜尋它，如果搜尋鍵沒有找到，但它在兩個鍵之間或所有鍵的左側或右側，並且存在指向另一個塊的指標在塊的左側或每個鍵的右側，然後遵循指標，直到搜尋成功或無法遵循任何塊。
使用 B 樹的原因是，當塊在插入鍵時變得滿時，可以透過將其分成三個部分來進行拆分，將其分成一個包含所有左邊的條目的塊，一個包含中間鍵的條目以及一個包含所有條目的塊在中間鍵的右邊，然後在從插入返回時將包含中間鍵的條目傳遞到父塊，然後父塊將其條目插入到其條目中，如果需要也會進行拆分。如果根節點拆分，則中間條目將成為一個單條目塊，該塊將成為根節點。在一系列插入過程中，這實際上是一種自平衡策略，並且樹在寬度而不是深度上增長，以便以後的搜尋主要在載入一個塊之後完成，並且在記憶體中進行寬度遍歷快速搜尋，而不是更不頻繁、更緩慢的垂直搜尋從磁碟載入未快取的子塊。
下面是一個記憶體中的 Java B 樹實現，可以像上面線性雜湊一樣，適用於基於磁碟的塊管理，只是需要稍微多一些跟蹤工作，例如使用顯式引用 ID 來表示塊，而不是引用塊，並將塊儲存在 map 中，其中 null 值表示未快取的塊。
[[[1]]] 為什麼作者現在放棄了二分查詢。
package btreemap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
/** can't work without setting a comparator */
public class BTreeMap<K, V> implements SortedMap<K, V> {
private static final int NODE_SIZE = 100;
BTBlock<K, V> root;
Comparator<? super K> comparator;
@Override
public Comparator<? super K> comparator() {
// TODO Auto-generated method stub
return comparator;
}
/**
*
* @param comparator
* - this is mandatory for the tree to work
*/
public void setComparator(Comparator<? super K> comparator) {
this.comparator = comparator;
root = new BTBlock<K, V>(NODE_SIZE, comparator);
}
/**
*
* @author syan
*
* @param <K>
* @param <V>
* the entry is associated with a right child block.
*
*/
static class BlockEntry<K, V> {
K k;
V v;
BTBlock right;
BlockEntry() {
}
BlockEntry(K k, V v) {
right = null;
this.k = k;
this.v = v;
}
}
/**
*
* @author syan - this represents the result of splitting a full block into
* a left block, and a right block, and a median key, the right
* block and the median key held in a BlockEntry structure as above.
* @param <K>
* @param <V>
* @param <V>g
*/
static class SplitRootEntry<K, V> {
BTBlock<K, V> left;
BlockEntry<K, V> entry;
SplitRootEntry(BTBlock<K, V> left, BlockEntry<K, V> entry) {
this.left = left;
this.entry = entry;
}
SplitRootEntry() {
super();
}
}
/**
* this is used to return a result of a possible split , during recursive
* calling.
*
* @author syan
*
* @param <K>
* @param <V>
*/
static class resultAndSplit<K, V> {
/**
* null , if there is no split.
*/
SplitRootEntry<K, V> splitNode;
V v;
resultAndSplit(V v) {
this.v = v;
}
resultAndSplit(SplitRootEntry<K, V> entry, V v) {
this.v = v;
this.splitNode = entry;
}
}
/**
* used to represent the insertion point after searching a block if compare
* is zero, then a match was found, and pos is the insertion entry if
* compare < 0 and pos == 0 , then the search ended up less than the
* leftmost entry else compare > 0 , and the search will be to the immediate
* right of pos.
*
* @author syan
*
*/
static class PosAndCompare {
int pos = 0;
int compare = 0;
}
static class BTBlock<K, V> {
List<BlockEntry<K, V>> entries;
BTBlock<K, V> leftBlock = null;
private int maxSz = 0;
Comparator<? super K> comparator;
Comparator<? super K> comparator() {
return comparator;
}
public BTBlock(int size, Comparator c) {
entries = new ArrayList<BlockEntry<K, V>>();
maxSz = size;
this.comparator = c;
}
/**
* PosAndCompare usage: if compare is zero, then a match was found, and
* pos is the insertion entry if compare < 0 and pos == 0 , then the
* search ended up less than the leftmost entry else compare > 0 , and
* the search will be to the immediate right of pos.
*
* @author syan
*
*/
private void blockSearch(K k, PosAndCompare pc) {
for (int i = 0; i < entries.size(); ++i) {
pc.compare = comparator.compare(k, entries.get(i).k);
if (pc.compare == 0) {
pc.pos = i;
return;
}
if (pc.compare < 0 && i == 0) {
pc.pos = 0;
return;
}
if (pc.compare < 0) {
pc.pos = i - 1;
pc.compare = 1;
return;
}
}
pc.pos = entries.size() - 1;
pc.compare = 1;
// binary search, it's hard to get it right !
// int left = 0;
// int right = entries.size();
//
// while (left <= right && left < entries.size()) {
// pc.pos = (right - left) / 2 + left;
// pc.compare = comparator().compare(k, entries.get(pc.pos).k);
// if (pc.compare < 0) {
// right = pc.pos-1;
// } else if (pc.compare > 0) {
// left = pc.pos+1;
// } else {
// break;
// }
// }
}
resultAndSplit<K, V> put(K k, V v) {
V v2;
if (entries.size() == 0) {
entries.add(new BlockEntry<K, V>(k, v));
return new resultAndSplit<K, V>(v);
} else {
PosAndCompare pc = new PosAndCompare();
blockSearch(k, pc);
// a match
if (pc.compare == 0) {
v2 = entries.get(pc.pos).v;
entries.get(pc.pos).v = v;
return new resultAndSplit<K, V>(v2);
}
BlockEntry<K, V> entry = new BlockEntry<K, V>(k, v);
// follow leftBlock if search is to left of first entry
if (pc.compare < 0 && pc.pos == 0 && leftBlock != null) {
resultAndSplit<K, V> result = leftBlock.put(k, v);
if (result.splitNode != null) {
leftBlock = result.splitNode.left;
entries.add(0, result.splitNode.entry);
}
} else if (pc.compare > 0 && entries.get(pc.pos).right != null) {
// follow right block if it exists
resultAndSplit<K, V> result = entries.get(pc.pos).right
.put(k, v);
if (result.splitNode != null) {
entries.get(pc.pos).right = result.splitNode.left;
entries.add(pc.pos + 1, result.splitNode.entry);
}
} else if (pc.compare < 0) {
// add to the left
entries.add(pc.pos, entry);
} else if (pc.compare > 0) {
// add to the right
entries.add(pc.pos + 1, entry);
}
// check if overflowed block , split if it has.
if (entries.size() > maxSz) {
int mid = entries.size() / 2;
// copy right half to new entries list.
List<BlockEntry<K, V>> rightEntries = new ArrayList<BlockEntry<K, V>>();
for (int i = mid + 1; i < entries.size(); ++i) {
rightEntries.add(entries.get(i));
}
BlockEntry<K, V> centreEntry = entries.get(mid);
BTBlock<K, V> rightBlock = new BTBlock<K, V>(maxSz,
comparator);
rightBlock.entries = rightEntries;
// the median entry's right block is the new right block's
// leftmost block
rightBlock.leftBlock = centreEntry.right;
// the new right block becomes the right block
centreEntry.right = rightBlock;
// reduce the old block's entries into its left half of
// entries.
for (int i = entries.size() - 1; i >= mid; --i)
entries.remove(i);
// create a return object, with the reduced old block as the
// left block
// and the median entry with the new right block attached
SplitRootEntry<K, V> split = new SplitRootEntry<K, V>(this,
centreEntry);
// the keyed value didn't exist before , so null
return new resultAndSplit<K, V>(split, null);
}
return new resultAndSplit<K, V>(v);
}
}
V get(K k) {
if (entries.size() == 0)
return null;
PosAndCompare pc = new PosAndCompare();
blockSearch(k, pc);
if (pc.compare == 0) {
return entries.get(pc.pos).v;
}
if (pc.compare < 0 && pc.pos == 0 && leftBlock != null) {
return leftBlock.get(k);
} else if (pc.compare < 0 && pc.pos == 0 && leftBlock == null) {
return null;
} else if (pc.compare > 0 && entries.get(pc.pos).right != null) {
return (V) entries.get(pc.pos).right.get(k);
} else
return null;
}
void getRange(SortedMap map, K k1, K k2) {
PosAndCompare pc = new PosAndCompare();
blockSearch(k1, pc);
PosAndCompare pc2 = new PosAndCompare();
blockSearch(k2, pc2);
for (int i = pc.pos; i <= pc2.pos; ++i) {
if (i == 0 && pc.pos == 0 && pc.compare < 0
&& leftBlock != null) {
leftBlock.getRange(map, k1, k2);
// if (pc2.pos == pc.pos)
// break;
}
/*
* add the entry if it exactly matches, or it is in range, but
* not if it is non-inclusive limit i.e. i == pc.pos and compare
* > 0
*/
if ((pc.compare == 0 && pc.pos == i) || i > pc.pos)
map.put(entries.get(i).k, entries.get(i).v);
if (entries.get(i).right != null) {
entries.get(i).right.getRange(map, k1, k2);
}
}
}
K headKey() {
if (leftBlock != null) {
return leftBlock.headKey();
}
return entries.get(0).k;
}
K tailKey() {
int i = entries.size() - 1;
if (entries.get(i).right != null) {
return (K) entries.get(i).right.tailKey();
}
return entries.get(i).k;
}
void show(int n) {
showTabs(n);
for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
System.err.print("#" + i + ":(" + e.k + ":" + e.v + ") ");
}
System.err.println();
showTabs(n);
if (leftBlock != null) {
System.err.print("Left Block\n");
leftBlock.show(n + 1);
} else {
System.err.println("No Left Block");
}
for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
showTabs(n);
if (e.right != null) {
System.err.println("block right of #" + i);
e.right.show(n + 1);
} else {
System.err.println("No block right of #" + i);
}
}
showTabs(n);
System.err.println("End of Block Info\n\n");
}
private void showTabs(int n) {
// TODO Auto-generated method stub
for (int i = 0; i < n; ++i) {
System.err.print(" ");
}
}
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
TreeMap<K, V> map = new TreeMap<K, V>();
root.getRange(map, fromKey, toKey);
return map;
}
@Override
public SortedMap<K, V> headMap(K toKey) {
// TODO Auto-generated method stub
return subMap(root.headKey(), toKey);
};
@Override
public SortedMap<K, V> tailMap(K fromKey) {
// TODO Auto-generated method stub
return subMap(fromKey, root.tailKey());
}
@Override
public K firstKey() {
// TODO Auto-generated method stub
return root.headKey();
}
@Override
public K lastKey() {
// TODO Auto-generated method stub
return root.tailKey();
}
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean containsKey(Object key) {
// TODO Auto-generated method stub
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}
@Override
public V get(Object key) {
// TODO Auto-generated method stub
return root.get((K) key);
}
@Override
public V put(K key, V value) {
resultAndSplit<K, V> b = root.put(key, value);
if (b.splitNode != null) {
root = new BTBlock<K, V>(root.maxSz, root.comparator);
root.leftBlock = b.splitNode.left;
root.entries.add(b.splitNode.entry);
}
return b.v;
}
@Override
public V remove(Object key) {
// TODO Auto-generated method stub
return null;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
// TODO Auto-generated method stub
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public Set<K> keySet() {
// TODO Auto-generated method stub
return null;
}
@Override
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
}
使用上述（帶有塊永續性的線性雜湊）資料結構作為持久儲存輔助索引 *1，此示例程式已應用於上述臨床用途。有趣的是，查詢結果識別了將糖尿病列為疾病的患者，以及合併症，以及存在時原子化的病理 HbA1c 資料，但通常在每個執業醫師下列出的患者要麼是非定期患者，要麼存在可疑的糖尿病診斷，而且查詢沒有檢查患者是否正在其他診所或內分泌科醫師處接受管理。
一項練習可能是將查詢重新表述為“將患者分組到執業醫師下，這些患者有糖尿病相關診斷和現有的 HbA1c 病理原子，但他們的最後一次 HbA1c 超過 6 個月”。這至少會選擇那些可能在某個階段接受諮詢執業醫師監測的患有糖尿病診斷的患者。
*1 BTreeMap 被用作普通紅黑樹 TreeMap 類的替代品，作為概念證明，並且在使用的資料集中實際上沒有發生記憶體溢位。線性雜湊用於透過 MapperImpl1 類實現表的 ur_no 索引。這是對於具有大量行的表（例如 PathAtom，以及肯定的 Progress）所必需的，因為索引太大而無法容納在執行在普通 2G Windows 桌面辦公電腦上的虛擬 Java 環境中。
package dbfmap.linux.test;
import java.io.IOException;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collection;
import java.util.Comparator;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Map.Entry;
import btreemap.BTreeMap;
import dbfmap.structs.DBFMemoPair;
import dbfmap.structs.DBFMemoPair.Iterator;
import dbfmap.use.Mapper;
import dbfmap.use.MapperImpl1;
public class FindDiabeticOverdue {
private static final int MAXINTERVALMONTHS_NOHBA1C = -6;
final static String RESULT = "PATHOL";
final static String RESULT_NAME_FIELD = "TESTNAME";
final static String RESULT_DATE = "REPORTDATE";
static String[] crossRefConditions = new String[] { "DIAB", "HEART", "MYOCARD",
"HYPERT", "HYPERC", "HYERL", "ANGIN", "CORON", "ISCHEM", "VASCUL" , "GOU", "METABO", "OBES" };
private BTreeMap<Date, List<String>> btree;
private Map<String, DBFMemoPair> dbfmap;
final DateFormat dateFormat = SimpleDateFormat
.getDateInstance(SimpleDateFormat.SHORT);
public Map<String, DBFMemoPair> getDbfmap() {
return dbfmap;
}
public FindDiabeticOverdue() throws IOException, ClassNotFoundException {
init();
}
void init() throws IOException, ClassNotFoundException {
Mapper m = MapperImpl1.getInstance();
dbfmap = m.getAccessObjectMap();
DBFMemoPair pairPat = dbfmap.get("PATIENTS");
DBFMemoPair accessResult= dbfmap.get(RESULT);
Iterator iResult = accessResult.iterator();
Map<String, Object> vv;
btree = new BTreeMap<Date, List<String>>();
btree.setComparator(new Comparator<Date>() {
@Override
public int compare(Date arg0, Date arg1) {
// TODO Auto-generated method stub
return arg0.compareTo(arg1);
}
});
Calendar calendarMaxIntervalNoHbA1c = GregorianCalendar.getInstance();
calendarMaxIntervalNoHbA1c.add(Calendar.MONTH, MAXINTERVALMONTHS_NOHBA1C);
// SortedMap before = btree.tailMap(c.getTime());
DBFMemoPair pairHist = dbfmap.get("HISTORY");
Iterator iHistory = pairHist.iterator();
Map<String, Object> vh;
BTreeMap<String, List<String>> bTreeConditionUrNos = new BTreeMap<String, List<String>>();
while ((vh = iHistory.readNextValues()) != null) {
String condition = (String) vh.get("CONDITION");
List<String> l = bTreeConditionUrNos.get(condition);
if (l == null) {
l = new LinkedList<String>();
}
l.add((String) vh.get("UR_NO"));
bTreeConditionUrNos.put(condition, l);
}
SortedMap<String, List<String>> diabetesUrNos = bTreeConditionUrNos.subMap("DIAB", "DIABZ");
SortedSet<String> patientUrNosWithDiabetes = new TreeSet<String>();
for (String s : diabetesUrNos.keySet()) {
System.out.println(s + diabetesUrNos.get(s).size() + " patients");
patientUrNosWithDiabetes.addAll(diabetesUrNos.get(s));
}
Map<String, Map<String, Object>> urNoToLastHbA1c = new HashMap<String, Map<String, Object>>();
for (String urno : patientUrNosWithDiabetes) {
List<Map<String, Object>> resultsOnePatient = accessResult.getRecords("UR_NO", urno);
for (Map<String, Object> result : resultsOnePatient) {
String testName = (String) result.get(RESULT_NAME_FIELD);
if (testName.startsWith("GLYCATED")) {
Map<String, Object> lastResult = urNoToLastHbA1c.get(urno);
if (lastResult == null
|| ((Date) result.get(RESULT_DATE)).after((Date) lastResult
.get(RESULT_DATE))) {
urNoToLastHbA1c.put(urno, result);
}
}
}
}
Map<String, Map<String, Object>> overdue = new TreeMap<String, Map<String, Object>>();
for (String urno : urNoToLastHbA1c.keySet()) {
Map<String, Object> lastResult = urNoToLastHbA1c.get(urno);
Date d = (Date) lastResult.get(RESULT_DATE);
if (d.before(calendarMaxIntervalNoHbA1c.getTime())) {
overdue.put(urno, lastResult);
}
}
List<String> noHbA1c = new ArrayList<String>(patientUrNosWithDiabetes);
noHbA1c.removeAll(urNoToLastHbA1c.keySet());
DateFormat f = SimpleDateFormat.getDateInstance(DateFormat.SHORT);
System.out.println("Those with No HbA1c =" + noHbA1c.size());
TreeMap<String, List<String> > responsibleTable = new TreeMap<String, List<String> > ();
for (String urno : noHbA1c) {
Seen seen = getResponsible(urno);
List<String> drsPatients = responsibleTable.get(seen.whoMost);
if ( drsPatients == null ) {
drsPatients = new ArrayList<String>() ;
responsibleTable.put(seen.whoMost,drsPatients);
}
drsPatients.add(urno);
}
for (String urno : overdue.keySet()) {
Seen seen = getResponsible(urno);
List<String> drsPatients = responsibleTable.get(seen.whoMost);
if ( drsPatients == null ) {
drsPatients = new ArrayList<String>() ;
responsibleTable.put(seen.whoMost,drsPatients);
}
drsPatients.add(urno);
}
for ( String dr : responsibleTable.keySet()) {
System.out.println("*********************** List for " + dr);
for ( String urNo : responsibleTable.get(dr)) {
List<Map<String, Object>> shouldBeOnePatientMap = pairPat.getRecords("UR_NO", urNo);
if (shouldBeOnePatientMap == null || shouldBeOnePatientMap.size() != 1) {
System.err
.println("ERROR with UR_NO for finding patient list : "
+ urNo
+ (shouldBeOnePatientMap == null ? " list " : "sz="
+ (String.valueOf(shouldBeOnePatientMap.size()))));
if (shouldBeOnePatientMap == null || shouldBeOnePatientMap.size() == 0)
continue;
}
Map<String, Object> patient = shouldBeOnePatientMap.get(0);
System.out.println(((String) patient.get("SURNAME")).trim() + ", "
+ ((String) patient.get("FIRSTNAME")).trim() + ", DOB:"
+ f.format(patient.get("DOB")));
DBFMemoPair atoms = dbfmap.get("PATHATOM");
List<Map<String, Object>> pathAtomsForOnePatient = atoms.getRecords("UR_NO", urNo);
boolean printedTest = false;
for (Map<String, Object> at2: pathAtomsForOnePatient ) {
String n = (String)at2.get("TESTNAME");
if ( n.toUpperCase().indexOf("A1C") >= 0 ) {
printedTest = true;
System.out.print( ", " + f.format(at2.get("RESULTDATE")) + " " + at2.get("RESULT").toString().trim() );
}
}
if ( printedTest)
System.out.println();
List<Map<String, Object>> conditions = pairHist.getRecords("UR_NO", urNo);
boolean printedCond = false;
for ( Map<String, Object> condition : conditions ) {
String conditionName = ((String)condition.get("CONDITION")).trim();
for ( String keyPart : crossRefConditions)
if ( conditionName.indexOf(keyPart)>= 0) {
if (!printedCond) System.out.print("Conditions: ");
System.out.print( " " + conditionName +":"+condition.get("YEAR"));
printedCond = true;
break;
}
}
if (printedCond)
System.out.println( );
}
System.out.println("**************** end of list for " + dr);
}
// for (String s : noHbA1c) {
// List<Map<String, Object>> l = pairPat.getRecords("UR_NO", s);
// if (l == null || l.size() != 1) {
// System.err
// .println("ERROR with UR_NO for finding patient list : "
// + s
// + (l == null ? " list " : "sz="
// + (String.valueOf(l.size()))));
// if (l == null || l.size() == 0)
// continue;
// }
// Map<String, Object> patient = l.get(0);
// System.out.println(((String) patient.get("SURNAME")).trim() + ", "
// + ((String) patient.get("FIRSTNAME")).trim() + ", DOB:"
// + f.format(patient.get("DOB")));
// List<Map<String, Object>> patConditions = pairHist.getRecords(
// "UR_NO", s);
// for (Map<String, Object> c2 : patConditions) {
// if (((String) c2.get("CONDITION")).indexOf("DIABE") >= 0) {
// System.out.println("\t" + (String) c2.get("CONDITION")
// + c2.get("YEAR"));
// }
// }
// Seen seen = showResponsible(s);
//
// }
//
// System.out.println("\n\nOVERDUE HbA1c ? = " + overdue.size());
//
// for (String s : overdue.keySet()) {
// Map<String, Object> res2 = overdue.get(s);
// List<Map<String, Object>> l = pairPat.getRecords("UR_NO", s);
// Map<String, Object> x = l.get(0);
// System.out.println(((String) x.get("SURNAME")).trim() + ", "
// + ((String) x.get("FIRSTNAME")).trim() + ", DOB:"
// + f.format(x.get("DOB")));
//
// System.out.println("\t" + f.format((Date)res2.get("REPORTDATE")) + " "+
// (String)res2.get(RESULT_NAME_FIELD) );
// DBFMemoPair atoms = dbfmap.get("PATHATOM");
// l = atoms.getRecords("UR_NO", s);
// for (Map<String, Object> at2: l ) {
// String n = (String)at2.get("TESTNAME");
// if ( n.toUpperCase().indexOf("A1C") >= 0 ) {
// System.out.print( "," + f.format(at2.get("RESULTDATE")) + " " + at2.get("RESULT") );
// }
// }
// System.out.println();
// showResponsible(s);
// }
}
private Seen showResponsible(String s) throws IOException,
ClassNotFoundException {
Seen seen = getResponsible(s);
System.out.println("Dr " + seen.whoMost + " saw " + seen.most
+ " times, out of total " + seen.total + "\n");
return seen;
}
static class Seen implements Comparable<Seen>{
int total;
int most;
String whoMost;
public Seen(int t, int m, String who) {
total = t;
most = m;
whoMost = who;
}
@Override
public int compareTo(Seen o) {
// TODO Auto-generated method stub
return whoMost.compareTo(o.whoMost);
}
}
private Seen getResponsible(String s) throws IOException,
ClassNotFoundException {
// TODO Auto-generated method stub
DBFMemoPair pairPat = dbfmap.get("PROGRESS");
List<Map<String, Object>> l = pairPat.getRecords("UR_NO", s);
TreeMap<String, Integer> countDr = new TreeMap<String, Integer>();
int total = 0;
for (Map<String, Object> m : l) {
String dr = (String) m.get("DR");
if (dr.indexOf("RECEPT") >= 0 || dr.indexOf("PRACTIT") >= 0)
continue;
++total;
Integer c = countDr.get(dr);
if (c == null)
countDr.put(dr, 1);
else
countDr.put(dr, c + 1);
}
TreeMap<Integer, String> ranking = new TreeMap<Integer, String>();
for (String d : countDr.keySet()) {
ranking.put(countDr.get(d), d);
}
Entry<Integer, String> e = ranking.lastEntry();
return new Seen(total, e.getKey(), e.getValue());
}
/**
* @param args
* @throws IOException
* @throws ClassNotFoundException
*/
public static void main(String[] args) throws IOException,
ClassNotFoundException {
// TODO Auto-generated method stub
FindDiabeticOverdue fdo = new FindDiabeticOverdue();
}
}
這個案例研究表明，“權衡”的計算機科學格言也適用於提高用於表示計算機化醫療記錄的技術複雜性。人們將企業級 SQL DBMS 的高階技術功能帶來的營銷效益與供應商鎖定、缺乏軟體可擴充套件性以及如果供應商決定關門大吉所需的昂貴資料提取成本的風險進行權衡。可以說，如果醫療記錄系統供應商沒有決定移除底層資料庫管理系統的所有功能，並使資料表和資料表架構的訪問變得不透明，這種情況就不會發生。它表明可擴充套件的資料庫管理只需要幾頁程式碼、一個好的演算法和一個開放的計算機語言系統，從人的角度來說，可以只僱用一名本地計算機科學畢業生來無限期地提供開源服務，以及另一名畢業生作為質量保證，以確保原始碼的可讀性，如果當前程式設計師決定不再提供服務。
有人可能會爭辯說，維持小型規模和家庭作坊式的普通實踐計算機醫療記錄狀態會破壞醫療資訊學標準化的需求以及電子醫療記錄在初級保健和醫院醫療保健之間的可移植性。但透過保持基於眾所周知、易於理解但可擴充套件的演算法的開放、可讀和可擴充套件架構，反駁論點是，合理的簡化有助於適應醫療編碼的未來需求，因為軟體對除少數幾個主導供應商以外的所有人來說都是不透明的。