代码之家 › 专栏 › 技术社区 › Joel Hooks

快速确定数据在阵列中的位置

loops data-structures arrays algorithm actionscript-3

Joel Hooks · 技术社区 · 16 年前

我有一个数据结构,如下图所示。我需要计算高亮显示单元格组右侧或左侧单元格的索引。

some data

您可以在下面的代码中看到,我天真地遍历每个索引的所有单元格,以确定请求的索引中是否有单元格。当我有几个(几百个)细胞时,这种方法非常有效,但当我有几千个细胞时,这种方法很快就会失效。

在这种特殊情况下,突出显示的组是移动的,并且只能在上一个/下一个占用的单元之前或之后移动到索引。所以groupMinX/maxX是它可以根据行中其他单元格的位置移动的最小和最大x值。

            private var movingGroup:CellGroup; //selected group

    public function getCellAtIndex(index:int):ICell
    {
        for each(var cell:ICell in cells)
        {
            if(cell.index==index)
                return cell;
        }

        return null;
    }

    public function groupMinX(xPos:Number):Number
    {
        var index:int = xPos/cellSize;
        var cellsOnLeft:Array = getAllCellsOnLeft(index-1);
        if(cellsOnLeft.length > 0)
            return cellsOnLeft[cellsOnLeft.length-1].x + cellSize;
        return 0;
    }

    public function groupMaxX(xPos:Number):Number
    {
        var index:int = xPos/cellSize;
        var cellsOnRight:Array = getAllCellsOnRight(index);
        if(cellsOnRight.length > 0)
            return cellsOnRight[0].x;
        return (maxIndex)*cellSize;
    }

    private function getAllCellsOnLeft(ofIndex:int):Array
    {
        var index:int = 1;
        var cells:Array = [];
        while( ofIndex >= 0 )
        {
            var cell:ICell = getCellAtIndex(ofIndex);
            if(cell && !movingGroup.containsCell(cell))
                cells.unshift( cell );
            ofIndex--;
        }
        return cells;       
    }

    private function getAllCellsOnRight(ofIndex:int):Array
    {
        var index:int = 1;
        var cells:Array = [];
        while( index <= maxIndex )
        {
            var cell:ICell = getCellAtIndex( ofIndex + index );
            if(cell && !movingGroup.containsCell(cell))
                cells.push( cell );
            index++;
        }
        return cells;       
    }

我要寻找的是扫描/跟踪细胞的有效方法。我循环的数组实际上不包含空白单元格,但它具有索引属性的单元格。

4 回复 | 直到 16 年前

Alan 16 年前

http://en.wikipedia.org/wiki/Linked_list

Joel Hooks 16 年前

由于列表是有序的,我建议您进行二进制搜索,以找到您想要的单元格。然后,不必在元素之间循环到左侧和右侧,只需将数组切片以形成左侧和右侧的两个新数组。

大概是这样吧,帕哈普斯(请原谅任何语法错误,我不知道actionscript…)

private function search(array:Array, index:int, low:int, high:int) :int 
{ 
  if (high < low)
    return -1 
  var middle:int = low + ((high - low) / 2) 
  if (array[middle].index > index)
    return search(array, index, low, middle - 1)
  else if (array[middle].index < index)
    return search(array, index, middle + 1, high)
  else
    return middle 
}  

private function sliceBitsOff(index:int)
{
   var index:int = search(yourArray, 7, 0, yourArray.length-1)
   var rightArray:Array = yourArray.slice(0, index - 1)
   var leftArray:Array = yourArray.slice(index + 1, yourArray.length)
}

Hamish Grubijan 16 年前

您可以预先缓存左侧单元格和右侧单元格的索引。。。

Chris Gutierrez 16 年前

我不确定这里是否遗漏了什么,但如果这是一个对象(单元)的数字索引数组,

cellsArr[cellsArr.indexOf(cellObj1) - 1] // previous cell    
cellsArr[cellsArr.indexOf(cellObj2) + 1] // get the cell after a "highlighted" cell