調整數組的速度

Question

因此，我正在編寫一個用Java編寫的Befunge解釋器。我幾乎把它全部倒下，除非我找不到解決Funge Space問題的好辦法。目前，我使用的是Befunge 93規格中規定的樣式，這是一個80x25陣列來存放代碼。儘管如此，在Funge中，我應該有一個「無限」的代碼數組（或者4,294,967,296 x 4,294,967,296，這兩個維度是-2,147,483,648到2,147,483,648），但顯然這樣做不是一個好主意分配的空間。但是，除此之外，創建一個新數組並在每次程序跳出界限時將每個字符複製到它中似乎不是一個好主意。有沒有解決這個問題，我錯過了？

所以基本上，我的問題是，我需要以某種方式擴展數組，每當我伸出界限，或使用某種其他數據結構。有什麼建議麼？

Funge 98 specs

另外，順便說一下，我還從來沒有弄清楚如何發音Befunge或Funge，我永遠都只是說它像「蜂funj」和「funj」

Answer 1

，而不必閱讀規範（不 - 我的意思是，只是NO！）：一個4,294,967,296 x 4,294,967,296數組顯然是一個高度理論化的構造，並且這些「數組條目」中只有很小一部分可以並且將會被使用。

除此之外：不管你是否使用數組或任何其他集合，你必須通過索引的問題：數組索引只能是int值，但4,294,967,296是兩倍Integer.MAX_VALUE（沒有簽名Java中的ints）。然而，表示這種「無限大」稀疏二維數組的一種方式是將長對數值（x和y座標）映射到數組條目的映射。大致如下：

import java.util.HashMap; 
import java.util.Map; 

interface Space<T> 
{ 
    void set(long x, long y, T value); 
    T get(long x, long y); 
} 

class DefaultSpace<T> implements Space<T> 
{ 
    private final Map<LongPair, T> map = new HashMap<LongPair, T>(); 

    @Override 
    public void set(long x, long y, T value) 
    { 
     LongPair key = new LongPair(x,y); 
     if (value == null) 
     { 
      map.remove(key); 
     } 
     else 
     { 
      map.put(key, value); 
     } 
    } 

    @Override 
    public T get(long x, long y) 
    { 
     return map.get(new LongPair(x,y)); 
    } 
} 


class LongPair 
{ 
    private final long x; 
    private final long y; 

    LongPair(long x, long y) 
    { 
     this.x = x; 
     this.y = y; 
    } 

    @Override 
    public String toString() 
    { 
     return "("+x+","+y+")"; 
    } 

    @Override 
    public int hashCode() 
    { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + (int) (x^(x >>> 32)); 
     result = prime * result + (int) (y^(y >>> 32)); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     LongPair other = (LongPair) obj; 
     if (x != other.x) 
      return false; 
     if (y != other.y) 
      return false; 
     return true; 
    } 

}