Найти минимальное положительное значение

Question

Какой лучший алгоритм для наименьшего ненулевого положительного значения из фиксированного числа (в данном случае 3) значений или возврата 0, если нет положительных вопросов?

Мой наивный подход ниже (в Delphi, но не стесняйтесь использовать все что угодно), но я думаю, что есть более элегантный способ.

value1Temp := MaxInt;
value2Temp := MaxInt;
value3Temp := MaxInt;

if ( value1T > 0) then
  value1Temp := value1;
if ( value2 > 0) then
  value2Temp := value2;
if ( value3 > 0) then
  value3Temp  := value3;

Result := Min(value1Temp, Min(value2Temp, value3Temp));
if Result = MaxInt then
  Result := 0;

Редактировать: Извините, что нужно, если нет положительных чисел. Я думал, что у меня там было раньше, но, должно быть, пропустил это.

Answer 1

Я бы сделал небольшую петлю (Это на C, я не парень из Delphi):

int maxPositiveValue(int *number, int listSize)
{
    int i, result = 0;

    for(i = 0; i < listSize; i++)
    {
        if(number[i] > 0 && (number[i] < result || result == 0))
            result = number[i];
    }

    return result;
}

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

ОБНОВЛЕНИЕ: Я изменил код в ответ на комментарии, которые я получил ниже.

Этот новый код немного сложнее, но теперь он будет обрабатывать:

1. Случай, когда список не содержит положительных целых чисел (возвращает 0).
2. Случай, когда список содержит один или несколько вхождений INT_MAX.
3. Список любой длины.

Answer 2

Я бы сделал это:

Результат: = MaxInt;
если значение1> 0, то Результат: = min (Результат, значение1);
если значение2> 0, то Результат: = min (Результат, значение2);
если значение3> 0, то Результат: = min (Результат, значение3);
если Result = MaxInt, то Result: = 0;

Если вы хотите, чтобы это было в цикле с произвольным числом вопросов, то:

Результат: = MaxInt;
для I: = от 1 до N до
если значение [I]> 0, то Результат: = мин (Результат, значение [I]);
если Result = MaxInt, то Result: = 0;

Если вы хотите, чтобы массив значений начинался с нуля, измените цикл for на: от 0 до N-1

Я думаю, этот код очень четко показывает, что именно делается.

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

Answer 3

Я не знаю Delphi, но вот быстрое решение в Ruby (предположим, что числа в списке)

[1,2,42,-12].delete_if{|n| n <= 0 }.min || 0

Алгоритмически вы удаляете все отрицательные (или 0) элементы, затем вы находите минимум. Если положительных элементов нет, [].min возвращает nil, поэтому итоговое || 0 дает запрошенный '0' в качестве ответа.

Answer 4

Как насчет следующей функции (в Delphi, конечно):

function LowestPositiveInt(IntArr : array of Integer):Integer;
var
  iX : integer;
  bValid : boolean;
begin
  Result := MaxInt;
  bValid := False;
  for ix := 0 to High(IntArr) do
    if (IntArr[ix] > 0) then
      begin
        bValid := true;
        if (IntArr[iX] < Result) then
          Result := IntArr[ix];
      end;
  if not bValid then
    Result := 0;
end;

затем назовите это следующим образом:

ShowMessage(IntToStr( LowestPositiveInt([5,2,3,-1,12]) ));

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

Result := LowestPositiveInt( [ Value1, Value2, Value3 ] );

EDIT Обновлено для обработки сценария LowestPosititiveInt ([MaxInt, MaxInt, MaxInt]) .

Answer 5

В DELPHI - если ваш домен представляет собой целые числа, и если вы можете поместить свои аргументы в longints, и если вы можете избежать передачи минимального целого числа ($ 80000000), то это даст вам желаемый результат без каких-либо условных переходов :

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   result := max(0,longint(
   min(longint((XX-1) xor $80000000),
   min(longint((YY-1) xor $80000000),
   longint((ZZ-1) xor $80000000)
   )) xor $80000000)+1);
end;

Техника зависит от обратимого преобразования без потерь типа longint, так что интересующий нас диапазон - целые числа от 1 до MAXINT - остается в порядке и занимает самые низкие значения. Простое переключение знакового бита почти дает то, что нам нужно, за исключением того, что мы не хотим, чтобы 0 входил в нижний диапазон. Вычитание 1 сначала (и добавление его позже) исправляет это. Используемая здесь операция xor расширяет оба операнда до int64, что требует явного приведения обратно к longint, поэтому функция min выдаст правильный результат. Наконец, если все операнды отрицательны, минимум будет найден в верхнем диапазоне, а ответ будет отрицательным. В этом случае мы хотим, чтобы ответ был 0, поэтому мы просто обрезаем его с помощью функции max.

Вот одна и та же математика, разбросанная по нескольким утверждениям для более удобного чтения:

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   // swap ordinal coding for range MININT..0 with range 1..MAXINT
   XX := XX-1;             // move region division to between 0 and 1
   XX := XX xor $80000000; // swap regions, preserving ordering
   XX := longint(XX);      // cram back into signed 32-bit
   // similarly with YY and ZZ
   YY := longint((YY-1) xor $80000000);
   ZZ := longint((ZZ-1) xor $80000000);
   // find min of three recoded values
   result := min(XX,min(YY,ZZ));
   // swap ordering back again
   result := result xor $80000000;  // swap regions, preserving ordering
   result := result+1;              // move region division back home
   result := longint(result);       // cram back into signed 32-bit
   // if all three were neg, result at this point is neg -- clip to zero
   result := max(0,result);
end;

-Аль.

Answer 6

Вы ищете эстетику или скорость?

Если последнее, я не могу придумать, как вы могли бы выполнить этот тест достаточно времени, чтобы его можно было обнаружить в приложении: это просто не имеет значения.

Приветствия

Answer 7

Требуется алгоритм выбора , если вы работаете с нефиксированным числом значений.

Однако, если вашему коду нужно проверять только три значения, вам следует избегать циклов и конкретных алгоритмов и просто сосредоточиться на микрооптимизации & mdash; в частности, как можно меньше ветвлений.

В Восхищение хакера , глава 4, где вы можете найти кое-что об этом введите ваше целое число со знаком в без знака, чтобы уменьшить число ветвей вдвое. Это сделано в функции smalllest_v2 () в C-коде ниже:

#include <stdio.h>
#include <limits.h>

int smallest_v1(int a, int b, int c)
{
        int min = INT_MAX;

        min = a>0 && a<min ? a : min;
        min = b>0 && b<min ? b : min;
        min = c>0 && c<min ? c : min;
}

// See Hacker's Delight, chapter 4.
int smallest_v2(int a, int b, int c)
{
        int min = INT_MAX;

        if ( (unsigned) a < min ) min = a;
        if ( (unsigned) b < min ) min = b;
        if ( (unsigned) c < min ) min = c;

        return min;
}

int main()
{
        printf("min v1: %d\n", smallest_v1(-10, 7, 3));
        printf("min v2: %d\n", smallest_v1(-10, 7, 3));
}

По сути, в книге сказано, что если вы хотите проверить, если

1 <= i <= 10

тогда это то же самое, что и сравнение без знака

(unsigned)(i - 1) <= 9

Книга также предлагает доказательство. Что вы получите, так это лучшее предсказание ветвления в вашем коде. Вы должны составить тестовую программу и рассчитать время.

Answer 8

Я согласен с Адамом. На самом деле вы не будете выполнять алгоритмически быстрее, чем линейный поиск, если вам нужен только наименьший натуральный номер в контейнере.

Его код должен выполняться довольно быстро, скорее всего, он будет переведен в CMOV в x86, поэтому оператор if внутри цикла for в любом случае не будет стоить столько

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

Answer 9

Небольшое улучшение предложения Джейсона, которое правильно обрабатывает пустые коллекции и коллекции, содержащие только отрицательные значения:

values.Min(r => r > 0 ? r : (int?)null) ?? 0

Answer 10

• Просмотрите значения списка, отбрасывая их, пока не найдете положительное значение, установите для него минимальное значение
• Просмотрите значения в остальной части списка
  • Если 0 <текущее значение <минимальное значение, установите минимальное значение на текущее значение </li>
• возвращаемое минимальное значение