Быстрое определение позиции данных в массиве - PullRequest
2 голосов
/ 16 декабря 2009

У меня есть структура данных, как показано на рисунке ниже. Мне нужно быстро вычислить индекс ячеек справа или слева от выделенной группы ячеек.

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;       
    }

То, что я ищу, - это эффективный метод сканирования / отслеживания ячеек. Массив, который я перебираю, на самом деле не содержит пустых ячеек, но имеет ячейки со свойством index.

Ответы [ 4 ]

1 голос
/ 16 декабря 2009

Поскольку список упорядочен, я бы посоветовал вам выполнить бинарный поиск, чтобы найти нужную ячейку. Затем вместо того, чтобы проходить по элементам слева и справа, просто нарежьте массив, чтобы сформировать два новых массива слева и справа.

Что-то вроде этого, parhaps? (прошу прощения за любые синтаксические ошибки, я не знаю actioncript ...)

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)
}
1 голос
/ 16 декабря 2009

Упс в моем твите я добавил не ту ссылку. Используйте связанный список. Пусть ваш класс Cell реализует интерфейс узла связанного списка. Не нужно зацикливать или использовать условные выражения.

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

0 голосов
/ 16 декабря 2009

Я не уверен, что здесь что-то отсутствует, но если это числовой индексный массив объектов (ячеек), Я думаю, вы могли бы сделать что-то вроде ...

cellsArr[cellsArr.indexOf(cellObj1) - 1] // previous cell    
cellsArr[cellsArr.indexOf(cellObj2) + 1] // get the cell after a "highlighted" cell
0 голосов
/ 16 декабря 2009

Вы можете просто предварительно кэшировать индексы ячейки слева и ячейки справа ... Ваш выбор структуры данных не идеален. Пожалуйста, опишите, что вы пытаетесь сделать на более высоком уровне. Была ли вам передана эта структура данных, или вы придумали ее?

...