Быстрое использование Sin/Cos пред вычисленный массив перевода

У меня есть следующий код, делающий функцию Sin/Cos использование предрасчетной таблицы памяти. в следующем примере таблица имеет 1024*128 объектов, покрывающих все значения Sin/Cos от 0 до 2pi. Я знаю, что могу использовать симметрию Sin/Cos и держать только 1/4 значений, но их у меня будет больше 'IFS' при вычислениях значения.

private const double PI2 = Math.PI * 2.0; 
private const int TABLE_SIZE = 1024 * 128;
private const double TABLE_SIZE_D = (double)TABLE_SIZE;
private const double FACTOR = TABLE_SIZE_D / PI2;

private static double[] _CosineDoubleTable;
private static double[] _SineDoubleTable;

Установите таблицу преобразования

private static void InitializeTrigonometricTables(){
   _CosineDoubleTable = new double[TABLE_SIZE];
   _SineDoubleTable = new double[TABLE_SIZE];

   for (int i = 0; i < TABLE_SIZE; i++){
      double Angle = ((double)i / TABLE_SIZE_D) * PI2;
      _SineDoubleTable[i] = Math.Sin(Angle);
      _CosineDoubleTable[i] = Math.Cos(Angle);
   }
}

Значение является двойным в радианах.

Value %= PI2;  // In case that the angle is larger than 2pi
if (Value < 0) Value += PI2; // in case that the angle is negative
int index = (int)(Value * FACTOR); //from radians to index and casted in to an int
double sineValue = _SineDoubleTable[index]; // get the value from the table

Я ищу более быстрый способ сделать это. Вышеупомянутые 4 строки составляют ~25% целого процесса (выполнил миллиарды времен).

15
задан Gilad 18 January 2010 в 18:17
поделиться

7 ответов

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

Результаты, основанные на 1'000'000'000 итераций со случайными значениями:

(1) 00:00:57.3382769  // original version
(2) 00:00:31.9445928  // optimized version
(3) 00:00:21.3566399  // Math.Sin

Код:

static double SinOriginal(double Value)
{
    Value %= PI2;
    if (Value < 0) Value += PI2;
    int index = (int)(Value * FACTOR);
    return _SineDoubleTable[index];
}

static unsafe double SinOptimized(double* SineDoubleTable, double Value)
{
    int index = (int)(Value * FACTOR) % TABLE_SIZE;
    return (index < 0) ? SineDoubleTable[index + TABLE_SIZE]
                       : SineDoubleTable[index];
}

Программа испытаний:

InitializeTrigonometricTables();
Random random = new Random();

SinOriginal(random.NextDouble());
var sw = System.Diagnostics.Stopwatch.StartNew();
for (long i = 0; i < 1000000000L; i++)
{
    SinOriginal(random.NextDouble());
}
sw.Stop();
Console.WriteLine("(1) {0}  // original version", sw.Elapsed);

fixed (double* SineDoubleTable = _SineDoubleTable)
{
    SinOptimized(SineDoubleTable, random.NextDouble());
    sw = System.Diagnostics.Stopwatch.StartNew();
    for (long i = 0; i < 1000000000L; i++)
    {
        SinOptimized(SineDoubleTable, random.NextDouble());
    }
    sw.Stop();
    Console.WriteLine("(2) {0}  // optimized version", sw.Elapsed);
}

Math.Sin(random.NextDouble());
sw = System.Diagnostics.Stopwatch.StartNew();
for (long i = 0; i < 1000000000L; i++)
{
    Math.Sin(random.NextDouble());
}
sw.Stop();
Console.WriteLine("(3) {0}  // Math.Sin", sw.Elapsed);
21
ответ дан 1 December 2019 в 01:10
поделиться

Я думаю, что myMethod4 может быть то, что вы имеете в виду, когда говорите: «Разве нельзя ссылаться на a.size и вызывать его, когда это необходимо?».

def myMethod1(f: Int => Unit): Unit = f(1)

def myMethod2(f: () => Int): Unit = {
  val value = f // f is function, taking no arguments, and returning an int.
                // we invoke it here.
  ()
}

def myMethod3(f: => Int): Unit = {
  val value = f // f is call by name parameter.
  ()
}

def myMethod4[A](f: A => Int, a: A): Unit = {
  val value = f(a)
  ()
}

import java.util.ArrayList

val a = new ArrayList[Int](1)
myMethod1((i: Int) => a.add(i))
myMethod1(a.add(_))     // shorthand for the above
myMethod2(() => a.size) // a.size is not evaluated, it is enclosed in an anonymous function definition.
myMethod3(a.size)       // a.size is not evaluated here, it is passed as a by-name parameter.
myMethod4((al: ArrayList[Int]) => al.size, a)
myMethod4((_: ArrayList[Int]).size, a)
myMethod4[ArrayList[Int]](_.size, a)
-121--4690938-

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

В скреуме вы тайм-бокс . И вы предоставляете только функции, которые работают.

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

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

-121--3279201-

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

  1. Используйте математическую библиотеку для конкретного процессора, например IKML или ACML и
    1. Вычислите значения в группах (векторах).
    2. Когда вам нужно и то, и другое, всегда вычисляйте одновременно грех и значение.
  2. Проверьте сложность алгоритма и конструкцию реализации.
  3. Убедитесь, что вы используете всю архитектуру процессора - x64, а также любые векторные команды, которые помогут.
4
ответ дан 1 December 2019 в 01:10
поделиться

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

  1. cos(x) = sin(pi/2-x).
  2. sin(pi + x) = -sin(x)

Вы можете сделать свой код непересекающимся. Сначала конвертируйте в формат int.

int index = (int)(Value * FACTOR);
index %= TABLE_SIZE; // one instuction (mask)
index = (index >= 0) ? index :TABLE_SIZE-index; // one instruction isel
double sineValue = _SineDoubleTable[index];

Все равно сравните с Math.Sin. Профиль Профиль Приофиль. (Промах с кэшем может замедлить ваш код в реальных примерах)

.
9
ответ дан 1 December 2019 в 01:10
поделиться

В CSS нет понятия «переменные», но я настоятельно рекомендую не делать то, что вы делаете. нет веской причины, по которой нельзя определить всю информацию о стиле в таблице CSS как классы CSS. Если вы сделаете это, а затем просто примените указанные классы в html и javascript, это одна большая нагрузка с точки зрения копирования и вставки.

Во-вторых, помните, что для элемента можно определить несколько классов CSS, например,

<div class='blue-text white-background'>my content</div>

Затем можно определить их независимо в CSS, a la:

.blue-text { color : Blue; }
.white-background { background-color: white;}

и вы даже можете создать правила, которые вступают в силу только при применении обоих правил:

.blue-text.white-background { color : AliceBlue; }

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

-121--2991205-

Это будет чертовски быстро.

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

[Edit] Я пропустил, насколько велики таблицы - это может значительно замедлить ваш код из-за промахов в кэше. Пробовали ли вы сравнивать его с Math.Cos () или другими методами аппроксимации триг-функций (вы можете получить очень хорошие аппроксимации с несколькими простыми умножениями, используя Taylor Series )

-121--2598262-

Это выглядит довольно хорошо, за исключением операции mod. Можете ли вы обойтись без него?

Если значения близки к нулю, вы можете использовать

while(Value > PI2) Value -= PI2;
while(Value < 0) Value += PI2;

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

2
ответ дан 1 December 2019 в 01:10
поделиться

Допустим, что разрешения для родительских папок правильные (т.е. все родительские папки должны иметь разрешение + x), попробуйте добавить:

shell=True

к команде Popen, например:

subprocess.Popen(("/Users/jondoe/development/mdb-export", mdb.name, tbl,), stdout=csv, shell=True)
-121--3090723-

Это расширенная функция PowerShell V2.0. Он немного длинный, но я проверил, что он дает один и тот же хэш-код (сгенерированный из растровых пикселей) на одной и той же картине, но с различными метаданными и размерами файла. Это версия с возможностью конвейера, которая также принимает подстановочные знаки и литеральные пути:

function Get-BitmapHashCode
{
    [CmdletBinding(DefaultParameterSetName="Path")]
    param(
        [Parameter(Mandatory=$true, 
                   Position=0, 
                   ParameterSetName="Path", 
                   ValueFromPipeline=$true, 
                   ValueFromPipelineByPropertyName=$true,
                   HelpMessage="Path to bitmap file")]
        [ValidateNotNullOrEmpty()]
        [string[]]
        $Path,

        [Alias("PSPath")]
        [Parameter(Mandatory=$true, 
                   Position=0, 
                   ParameterSetName="LiteralPath", 
                   ValueFromPipelineByPropertyName=$true,
                   HelpMessage="Path to bitmap file")]
        [ValidateNotNullOrEmpty()]
        [string[]]
        $LiteralPath
    )

    Begin {
        Add-Type -AssemblyName System.Drawing
        $sha = new-object System.Security.Cryptography.SHA256Managed
    }

    Process {
        if ($psCmdlet.ParameterSetName -eq "Path")
        {
            # In -Path case we may need to resolve a wildcarded path
            $resolvedPaths = @($Path | Resolve-Path | Convert-Path)
        }
        else 
        {
            # Must be -LiteralPath
            $resolvedPaths = @($LiteralPath | Convert-Path)
        }

        # Find PInvoke info for each specified path       
        foreach ($rpath in $resolvedPaths) 
        {           
            Write-Verbose "Processing $rpath"
            try {
                $bmp    = new-object System.Drawing.Bitmap $rpath
                $stream = new-object System.IO.MemoryStream
                $writer = new-object System.IO.BinaryWriter $stream
                for ($w = 0; $w -lt $bmp.Width; $w++) {
                    for ($h = 0; $h -lt $bmp.Height; $h++) {
                        $pixel = $bmp.GetPixel($w,$h)
                        $writer.Write($pixel.ToArgb())
                    }
                }
                $writer.Flush()
                [void]$stream.Seek(0,'Begin')
                $hash = $sha.ComputeHash($stream)
                [BitConverter]::ToString($hash) -replace '-',''
            }
            finally {
                if ($bmp)    { $bmp.Dispose() }
                if ($writer) { $writer.Close() }
            }
        }  
    }
}
-121--3113870-

Нет гарантии, что это принесет много пользы, но в зависимости от вашего процессора, целочисленная математика часто быстрее, чем математика с плавающей точки. Конечно, как указал BleyRaja, использование C++ также почти наверняка поможет. Использование языка сборки, вероятно, не принесет много пользы - для такого поиска таблицы компилятор C++ может обычно производить довольно хороший код.

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

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

2
ответ дан 1 December 2019 в 01:10
поделиться

Можно попробовать использовать тот факт, что cos(x) = sin(x + pi/2). И сделать синусоидальную таблицу на одну четверть больше, чтобы вы могли повторно использовать ее как косинусоидальную таблицу, начинающуюся на одну четверть. Не уверен, что C# позволяет вам получить указатель на середину таблицы, как это сделал бы C. Но даже если нет, уменьшенное использование кэша может стоить больше, чем добавленное время для смещения в синусоидальную таблицу.

То есть, выражено в C:

double* _CosineDoubleTable = &_SineDoubleTable[TABLESIZE / 4];
0
ответ дан 1 December 2019 в 01:10
поделиться

Это и так будет чертовски быстро.

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

[Правка] Я пропустил, насколько большие таблицы - это вполне может значительно замедлить ваш код из-за промахов в кэше. Вы пробовали сравнивать его с Math.Cos(), или другими методами аппроксимации триггерных функций (Вы можете получить очень хорошие аппроксимации с несколькими простыми умножениями, используя Taylor Series)

.
0
ответ дан 1 December 2019 в 01:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: