如何重新索引稀疏关联数组 [英] how to reindex a sparse associative array

问题描述

首先，这个问题是不是涉及到一个特定的语言 - 我用HAXE瞄准多个平台 - 这样一个伪code将绰绰有余

下面是我的问题：我有一个稀疏矩阵描述这种形式

 边缘=
[
1,1,2,1,3,1,4,1，
2,2,3,2，
3,3,4,3,5,3，
4,4,5,4,6,4，
5,5,6,5,7,5,25,5,27,5,28,5,29,5,30,5
]。
 

此描述边缘协会：

• 点1连接至点1，2，3及4
• 点2连接至点2及3
• 点3被连接到分3，4和5
• 点4被连接到分4，5和6
• 在5个点的挂点5，6，7，25，27，28，29安培; 30

现在我需要使这个在3D和这样做，我需要COM preSS中的数据为索引缓存没有差距。 说上面的例子，我需要得到：

  newEdges =
[
1,2，1,3，1，4，
2,3，
3,4-，3,5-，
4,5，4,6，
5,6，5,7，5,8，5,9，5,10 5,11，5,12
]
 

所以，边缘连接本身（边1-1，2-2，3-3等）必须被移除（容易）。

为点顺序并不重要（边缘1-2 =边缘2-1），我们也将删除重复的边缘（在某种程度上容易）。

现在棘手的部分是去掉了空白：作为7是连续的最高值，25是一个正确后，​​25必须成为8，27必须成为9，28必须成为10等

现在我使用的BitmapData中，我绘制所有的值作为XY坐标。 然后我递归此位图中的非空的垂直条纹（1个像素宽的矩形）复制彼此相邻到临时位图。 然后，我做同样的横条纹，最后扫描我的位图和存储X'放大器;像素的边缘ID的Y值。

和它的作品！（至少它似乎:)） 但是开销是可怕和根据输入矩阵，我可能只是不能够产生的位图（例如闪光限于4092个像素最大值，JS不支持copyPixels很好）。

所以，问题是你会怎么做这个差距去除无位图，没有一个特定语言的方法是什么？

希望这是明显不够的， 感谢您的关注。

萨科

解决方案

让 E [M + 1] [M + 1] 将2维邻接矩阵对应以边缘，其中点指数的取值范围为[0..m]。

让 F [N] 是一个有序数组的 N 参观点边缘。 通过创建 F [N] 阵列，我们正在创建和非连续点指数之间的映射范围是[0..m]从连续点指数[ 0到n-1]。

创建一个新的邻接矩阵如下：

 对于i = 0 ..（N-1）
    对于j = 0 ..（N-1）//或，J =第（i + 1）..（N-1）为上三角部
        政[I] [J] = E [F [I] [F [J]
    结束
结束
 

这将只需要为O（n ^ 2），而不是O（平方公尺）的时间。

编辑：删除了如果语句。如果这两个E和G被初始化为全0这是不必要的。

first off, this question is not related to a specific language - I use Haxe to target multiple platforms - so a pseudo code will be more than enough.

here's my problem : I have a sparse Matrix description in this form:

edges = 
[
1,1,2,1,3,1,4,1,
2,2,3,2,
3,3,4,3,5,3,
4,4,5,4,6,4,
5,5,6,5,7,5,25,5,27,5,28,5,29,5,30,5
];

this describes edges associations:

• point 1 is linked to points 1, 2, 3 & 4
• point 2 is linked to points 2 & 3
• point 3 is linked to points 3, 4 & 5
• point 4 is linked to points 4, 5 & 6
• point 5 is linked to points 5, 6, 7, 25, 27, 28, 29 & 30

now I need to render this in 3D and to do so, I need to "compress" the data into an index buffer without "gaps". say with the above example, I'd need to get :

newEdges = 
[ 
1,2, 1, 3, 1, 4,
2,3,
3,4, 3,5,
4,5, 4,6,
5,6, 5,7, 5,8, 5,9, 5,10, 5,11, 5,12
]

so, the edge linking themselves (edge 1-1, 2-2, 3-3 etc. ) must be removed (easy).

as the point order is not important ( the edge 1-2 = edges 2-1 ) we shall also remove the duplicate edges (sort of easy).

now the tricky part is to remove the "gaps": as 7 was the highest consecutive value and 25 is the one right after, 25 must become 8, 27 must become 9, 28 must become 10 and so on.

for now I'm using a BitmapData in which I plot all the values as XY coordinates. then I recursively copy the non empty vertical stripes (1 pixel wide rect) of this bitmap next to each other into a temporary bitmap. then I do the same for the horizontal stripes and finally scan my bitmap and store X & Y values of the pixels as edges' IDs.

and it works!( at least it seems to :) ) but the overhead is terrible and depending on the input Matrix, I might just not be able to generate the Bitmaps (for instance flash is limited to 4092 pixels max, JS doesn't support copyPixels very well).

so the question is how would you do this "gap removal" without bitmaps and without a language-specific method?

hoping this was explicit enough, thanks for your attention.

Nicolas

解决方案

Let E[m+1][m+1] be the 2-dimensional adjacency matrix corresponding to edges, where the range of point indices is [0..m].

Let f[n] be a sorted array of the n points visited in edges. By creating the f[n] array we're creating a mapping between the non-contiguous point indices in the range [0..m] and the contiguous point indices from [0..n-1].

Create a new adjacency matrix G as follows:

for i = 0..(n-1)
    for j = 0..(n-1)    // or, j = (i+1)..(n-1) for upper triangular portion
        G[i][j] = E[f[i]][f[j]]
    end
end

This will only take O(n^2) rather than O(m^2) time.

Edit: Removed the if statement. If both E and G are initialized to all 0's it's unnecessary.

这篇关于如何重新索引稀疏关联数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！