Упростить / Neatify этот двусторонний цикл? - PullRequest
Новая
       6

Упростить / Neatify этот двусторонний цикл?

1 голос
/ 11 сентября 2010

У меня где-то пересеклись провода (или я не выспался). Мне нужен двусторонний цикл, и мой текущий код просто безобразен.

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

Пример: 120.121.119.122.118.123.117, ...

У меня есть критерий остановки, который необходимо соблюдать для каждого направления в отдельности. Если это встречается для одного направления, я только хочу бежать в другом направлении, если оба встречаются, мне нужно выйти из цикла. Кроме того, мне нужно остановиться, если следующий индекс недопустим (конец структуры данных, скажем, меньше 0 или больше 200).

Пример: Остановка выполнения на 116 назад и на 130 вперед: 120.121.119.122.118.123.117.124.116 (перерыв), 125.126.127.128.129.130.

Сначала бежать в одном направлении, затем, к сожалению, другое.

Мой текущий код просто ужасен. Много строк без какого-либо «производительного» кода. Только логика итерации: 

  int start_idx = 120;
  int forward_idx = start_idx;
  int backward_idx = start_idx;

  bool next_step_forward = true; //should next step be forward or backward?

  int cur_idx;
  while(backward_idx >= 0 || forward_idx >= 0)
  {
    if(next_step_forward   //if we should step forward
      && forward_idx >= 0) //and we still can step forward
    {
      cur_idx = ++forward_idx;

      if(forward_idx >= 200) //200 is fictive "max index"
      {
        next_step_forward = false;
        forward_idx = -1; //end of data reached, no more stepping forward
        continue;
      }

      if(backward_idx >= 0)
      {
        next_step_forward = false;
      }
    }
    else if(!next_step_forward 
            && backward_idx >= 0)
    {
      cur_idx = --backward_idx;
      if(backward_idx < 0) //beginning of data reached, no more stepping backward
      {
        next_step_forward = true;
        continue;
      }

      if(forward_idx >= 0)
      {
        next_step_forward = true;
      }
    }
    else
    {
      next_step_forward = !next_step_forward; //ever hit?, just security case
      continue; 
    }

    //loop body
    //do something with cur_idx here

    if(stoppingCriterionMet())
    {

      if(cur_idx > start_idx)
      { //this was a forward step, stop forward stepping
        forward_idx = -1;
      }
      else
      { //this was backward step, stop backward stepping
        backward_idx = -1;
      }
    }
  }

Я что-то упустил? Любые намеки приветствуются. Спасибо.

Редактировать 1: Есть много очень хороших ответов, которые помещают «сделать что-то с cur_idx» в отдельную функцию. Хотя это идеальная идея для моего вопроса, я предпочитаю размещать итеративный код в другом месте и оставлять там производительный код. У меня длинный алгоритм, и я хочу разделить его после завершения, чтобы минимизировать работу по перестановке.

Ответы [ 4 ]

2 голосов
/ 11 сентября 2010

Как насчет этого? 

void do_loop(SomeType *arr, int start, int low, int high, int arr_max)
{
    int downwardIndex, upwardIndex;
    downwardIndex = upwardIndex = start;
    while (downwardIndex > 0 && upwardIndex < arr_max) {
        if (downwardIndex < low && upwardIndex > high) {
            break;
        }
        if (downwardIndex > low) {
            processElement(arr[downwardIndex]);
            downwardIndex--;
        }
        if (upwardIndex < high) {
            processElement(arr[upwardIndex]);
            upwardIndex++;
        }
    }
}
1 голос
/ 11 сентября 2010

Первый шаг при взломе этого (при условии, что C - адаптация необходима для других языков, но концепции в основном не зависят от языка): 

void pass1(int start_x, int lo_limit, int hi_limit)
{
    assert(start_x >= lo_limit && start_x <= hi_limit);
    int lo_x = start_x - 1;
    int hi_x = start_x + 1;

    Process(start_x);
    if (StopCriterion(start_x))
        return;  // Is that correct?

    while (lo_x >= lo_limit && hi_x <= hi_limit)
    {
        Process(lo_x);
        if (StopCriterion(lo_x))
            lo_x = lo_limit - 1;
        else
            lo_x--;
        Process(hi_x);
        if (StopCriterion(hi_x))
            hi_x = hi_limit + 1;
        else
            hi_x++;
    }
    while (lo_x >= lo_limit)
    {
        Process(lo_x);
        if (StopCriterion(lo_x))
            lo_x = lo_limit - 1;
        else
            lo_x--;
    }
    while (hi_x <= hi_limit)
    {
        Process(hi_x);
        if (StopCriterion(hi_x))
            hi_x = hi_limit + 1;
        else
            hi_x++;
    }
}

Непонятно, что должно произойти, если начальная позиция соответствует критерию остановки. Должен ли поиск вообще остановиться, или он должен продолжаться вверх, или вниз, или в обе стороны. Я выбрал «полностью прекратить», но можно было бы рассмотреть любой из перечисленных вариантов. В случае «обоих» вы даже не потрудитесь выполнить проверку критерия остановки.

Я также решил сделать нижнее перед верхним направлением; это явно тривиально наоборот. Порядок последних двух циклов не имеет значения, потому что, если оба направления заканчиваются в одной и той же итерации, ни один завершающий цикл не выполняется; если прервано только одно направление, соответствующий цикл не будет выполнен вообще - будет выполняться только другое.

Так как там есть повторяющийся код: 

void pass2(int start_x, int lo_limit, int hi_limit)
{
    assert(start_x >= lo_limit && start_x <= hi_limit);
    int lo_x = start_x - 1;
    int hi_x = start_x + 1;

    Process(start_x);
    if (StopCriterion(start_x))
        return;  // Is that correct?

    while (lo_x >= lo_limit && hi_x <= hi_limit)
    {
        Process_lo(&lo_x, lo_limit);
        Process_hi(&hi_x, hi_limit);
    }
    while (lo_x >= lo_limit)
        Process_lo(&lo_x, lo_limit);
    while (hi_x <= hi_limit)
        Process_hi(&hi_x, hi_limit);
}

void Process_lo(int *lo_x, int lo_limit)
{
    Process(*lo_x);
    if (StopCriterion(*lo_x))
        *lo_x = lo_limit - 1;
    else
        *lo_x--;
}

void Process_hi(int *hi_x, int hi_limit)
{
    Process(*hi_x);
    if (StopCriterion(*hi_x))
        *hi_x = hi_limit + 1;
    else
        *hi_x++;
}

Элементы управления видимостью (статические функции) и т. Д. Опущены в качестве подробностей языка реализации.

1 голос
/ 11 сентября 2010

Так получилось, что сегодня я закодировал почти эту проблему. И я использовал функцию итератора C #, чтобы сделать это. Но я думаю, что вы хотите более общее решение.

Если вы используете язык, на котором вы можете создавать свои собственные итераторы (C ++, Java, C #), это легко. Вы просто создаете пользовательский итератор, который изначально выплевывает числа, начиная с центра. Затем вы даете итератору дополнительную функцию, чтобы он прекратил работу в текущем направлении.

Если вы делаете что-то подобное в C (для меня это выглядит как C), вы можете имитировать это с помощью структуры, содержащей состояние итератора и функции, которые вы вызываете для продвижения вперед или остановки.

0 голосов
/ 11 сентября 2010

Вот как я подхожу к этому в C #: 

const int UPPER_BOUND = 200;
const int LOWER_BOUND = 0;
const int START = 120;
bool foundlower = false, foundupper = false;
int upper, lower; 
upper = lower = START;

while (!foundlower || !foundupper) {
    if (!foundlower) {
        if (--lower <= LOWER_BOUND) foundlower = true;
        if (stoppingCriterionMet(lower)) foundlower = true;
    }

    if (!foundupper) {
        if (++upper >= UPPER_BOUND) foundupper = true;
        if (stoppingCriterionMet(upper)) foundupper = true;
    }
}
...