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

В Haskell, как обычно, его самое легкое, чтобы решить общую проблему и затем объявить особый случай.

foo xs = let xs1 = filter (>0) xs in if null xs1 then 0 else minimum xs1

foo3 x1 x2 x3 = foo [x1, x2, x3]

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

Я вижу слишком много строк кодов для тех, которые пытаются решить общую проблему в C#. Если значения IEnumerable<int> затем

values.Select(v => (int?)v)
      .Where(v => v > 0)
      .Min() ?? 0;

возвращает самое маленькое положительное значение в values если Вы существуете иначе, это возвращается 0. Здесь, я использую факт это Enumerable.Min(IEnumerable<int?>) возвратится null если последовательность пуста. Так, мы отфильтровываем неположительные значения и затем находим минимум. Если все значения неположительны, мы получаем нуль, как желаемый и иначе находим минимум положительных значений.

Это работает, каков тип элементов массива

template <typename T>
T min_pos(T* a, int n)
{
    int i /* = 0 */ /* Edit: commented this out */;

    // Find the first positive element in the array
    for (i = 0; i < n; ++i)
        if (a[i] > 0)
            break;

    // If no positive element was found, return 0
    if (i == n)
        return 0;

    T res = a[i];

    // Search the rest of the array for an element
    // that is positive yet smaller than res
    for (++i; i < n; ++i)
    {
        if ((a[i] > 0) && (a[i] < res))
            res = a[i];
    }

    return res;
}

Это - C#

public int GetSmallestPositive(IList<int> pValues)
{
    if(pValues == null)
    {
        throw new ArgumentNullException("pValues");
    }
    int _negNumCount = 0;
    int _smallest = int.MaxValue;
    for(int i = 0; i < pValues.Count; ++i)
    {
        if(pValues[i] < _smallest)
        {
            if(pValues[i] <= 0)
            {
                ++_negNumCount;
                continue;
            }
            _smallest = pValues[i];
            if(_smallest == 1)
            {
                return 1;
            }
        }
    }
    return (_negNumCount == pValues.Count) ? 0 : _smallest;
}

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

Править: Зафиксированный для возврата 0, если список полон отрицательных чисел. Выдайте исключение, если pValues является пустым.

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

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

Здесь версия C, поющая в припеве прочь решения в сообщении вопроса, но фиксирует случай, где всеми значениями является MaxInt...

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    if (value1Temp == 0) { value1Temp = tempMax; }
    if (value2Temp == 0) { value2Temp = tempMax; }
    if (value3Temp == 0) { value3Temp = tempMax; }
    return min(value1Temp, min(value2Temp, value3Temp));
}

Это также возможно сделать это способом без ответвлений, с минуты и макс. может быть реализовано как операции без ответвлений:

int min(int x, int y)
{
    return y + ((x - y) & -(x < y));
}

int max(int x, int y)
{
    return x - ((x - y) & -(x < y));
}

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax, mask;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    mask = -(value1Temp > 0);
    value1Temp = (value1Temp & mask) | (tempMax & ~mask);
    mask = -(value2Temp > 0);
    value2Temp = (value2Temp & mask) | (tempMax & ~mask);
    mask = -(value3Temp > 0);
    value3Temp = (value3Temp & mask) | (tempMax & ~mask);
    return min(value1Temp, min(value2Temp, value3Temp));
}

Для большего количества фона на том, почему Вы когда-либо хотели бы сделать это, см.: "То, если" Дорог? и Взломы Битового жонглирования.

Править: Ударенный на мою более раннюю попытку решения без ответвлений, которое на самом деле не работало. Добавленный новое решение без ответвлений, которое должно работать.

c# версия, которая покрывает все основания (я думаю):

public int GetMinimumPositiveValue(IEnumerable<int> values)
{
    int result = int.MaxValue;
    bool hasPositiveValue = false;

    foreach (int value in values)
    {
        if(value == 1) { return value; } 

        if(value > 0)
        {
            hasPositiveValue = true;

            if(value < result)
            {
                result = value;
            }
        }
    }

    return hasPositiveValue ? result : 0;
}

Вот то, что я придумал после размышления об этом немного больше

Result := 0;
if value1 > 0 then
  Result := value1;
if (value2 > 0) and ((Result = 0) or (value2 < Result)) then
  Result := value2;
if (value3 > 0) and ((Result = 0) or (value3 < Result)) then
  Result := value3;

Предоставил, есть ли у Вас список, более универсальные алгоритмы лучше.

Result := Min(IfThen(Value1 > 0, Value1, MAXINT), 
              Min(IfThen(Value2 > 0, Value2, MAXINT),
                  IfThen(Value3 > 0, Value3, MAXINT)));

Цикл не будет работать, если исходные данные не будут списком/массивом на вопрос.

Не ясно из вопроса, что должна сделать функция, если ни один из этих трех не является положительным и ненулевым.

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

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

Удачи

То, что Вы хотите, является алгоритмом выбора, если Вы работаете с непостоянным числом значений.

Однако, если Ваш код только должен проверить три значения, необходимо избежать циклов и определенных алгоритмов, и просто concentrace на микрооптимизации — а именно, как можно меньше ветвления.

Существует некоторый материал об этом в Восхищении Хакера, главе 4, где можно преобразовать тип целого числа со знаком к неподписанному для сокращения вдвое количества ответвлений. Это сделано в функции smallest_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

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

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

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

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

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

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;

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

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

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;

- Al.

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

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

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

Я сделал бы немного цикла (Это находится в 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. Список любой длины.

Как насчет следующей функции (в 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 ] );

РЕДАКТИРОВАНИЕ, Обновленное для обработки LowestPosititiveInt ([MaxInt, MaxInt, MaxInt]) сценарий.

//return the smallest non-zero positive number, or null.
//relying on Min or Max is considered cheating.
public static int? smallestNonZeroPositiveNumberOfThree(
    int val1, int val2, int val3)
{
    //we have no guarantee that any of the 3 inputs will be positive
    int? result = null;
    if (val1 > 0) 
    {
        result = val1; 
        if (val2 > 0 && val2 < result) { result = val2; }
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val2 > 0)
    {
        result = val2; 
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val3 > 0)
    {
        result = val3; 
    }
    return result;
}