7

a整数の配列q(最大 100,000)に対して1 つの整数を XOR する必要があります。つまり、ループしている場合は、

XOR q[0]

XOR q[1]

.....

a XOR q[100000]

(10万回)

aXORされる一連のそのようなものがあります。

必要な入力を渡すコンソール アプリケーションを作成しています。

組み込みの C#^演算子を使用して XOR 操作を実行しています。他に方法はありますか？

整数をバイト配列に変換し、各ビットを XOR して最終結果を計算するのは良い考えでしょうか?

入力 (2 行の間にスペースを入れないでください)

1

15 8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 6 10

1023 7 7

33 5 8

182 5 10

181 1 13

5 10 15

99 8 9

33 10 14

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace XOR
{
    class Solution
    {
        static void Main(string[] args)
        {

            List<TestCase> testCases = ReadLine();
            //Console.WriteLine(DateTime.Now.ToLongTimeString());
            CalculationManager calculationManager = new CalculationManager();

            foreach (var testCase in testCases)
            {
                var ints = testCase.Queries.AsParallel().Select(query => calculationManager.Calculate(query, testCase.SequenceOfIntegers)).ToList();
                ints.ForEach(Console.WriteLine);
            }

            //Console.WriteLine(DateTime.Now.ToLongTimeString());
            //Console.ReadLine();
        }

        private static List<TestCase> ReadLine()
        {
            int noOfTestCases = Convert.ToInt32(Console.ReadLine());
            var testCases = new List<TestCase>();

            for (int i = 0; i < noOfTestCases; i++)
            {
                string firstLine = Console.ReadLine();
                string[] firstLineSplit = firstLine.Split(' ');
                int N = Convert.ToInt32(firstLineSplit[0]);
                int Q = Convert.ToInt32(firstLineSplit[1]);

                var testCase = new TestCase
                                   {
                                       Queries = new List<Query>(),
                                       SequenceOfIntegers = ReadLineAndGetSequenceOfIntegers()
                                   };

                for (int j = 0; j < Q; j++)
                {
                    var buildQuery = ReadLineAndBuildQuery();
                    testCase.Queries.Add(buildQuery);
                }

                testCases.Add(testCase);
            }

            return testCases;
        }

        private static List<int> ReadLineAndGetSequenceOfIntegers()
        {
            string secondLine = Console.ReadLine();
            List<int> sequenceOfIntegers = secondLine.Split(' ').ToArray().Select(x => Convert.ToInt32(x)).ToList();
            return sequenceOfIntegers;
        }

        private static Query ReadLineAndBuildQuery()
        {
            var query = Console.ReadLine();
            List<int> queryIntegers = query.Split(' ').ToArray().Select(x => Convert.ToInt32(x)).ToList();
            Query buildQuery = ReadLineAndBuildQuery(queryIntegers[0], queryIntegers[1], queryIntegers[2]);
            return buildQuery;
        }

        private static Query ReadLineAndBuildQuery(int a, int p, int q)
        {
            return new Query { a = a, p = p, q = q };
        }


    }

    class CalculationManager
    {
        public int Calculate(Query query, List<int> sequenceOfIntegers)
        {
            var possibleIntegersToCalculate = FindPossibleIntegersToCalculate(sequenceOfIntegers, query.p, query.q);
            int maxXorValue = possibleIntegersToCalculate.AsParallel().Max(x => x ^ query.a);
            return maxXorValue;
        }

        private IEnumerable<int> FindPossibleIntegersToCalculate(List<int> sequenceOfIntegers, int p, int q)
        {
            return sequenceOfIntegers.GetRange(p - 1, (q - p) + 1).Distinct().ToArray();
        }
    }

    class TestCase
    {
        public List<int> SequenceOfIntegers { get; set; }
        public List<Query> Queries { get; set; }
    }

    class Query
    {
        public int a { get; set; }
        public int p { get; set; }
        public int q { get; set; }
    }
}
4

4 に答える 4

16

^ビット単位のxor演算子を使用するのが、整数をxorする最も速い方法です。

この操作は、単一のアトミックプロセッサ操作に変換されます。

あなたが分解で見ることができるように：

        int i = 4;
00000029  mov         dword ptr [ebp-3Ch],4 
        i ^= 3;
00000030  xor         dword ptr [ebp-3Ch],3

したがって、コードをより高速に実行したい場合は、xorメソッドではなく、アルゴリズム/アプローチ（Marc Gravellによって提案された）を変更する必要があります。

于 2012-05-12T23:04:12.127 に答える
5

私が試した唯一のことは（intアプローチが遅すぎると考える理由がある場合）、unsafeコードを使用してそれぞれint[]をとして扱い、32の代わりにlong*64ビット演算を使用することです（ここでも^）、半分反復、および少し少ない間接参照。IIRCは、私がいくつかのWebソケットコードに対して行ったこととほぼ同じです（クライアントからサーバーへのメッセージにWebソケットマスクを適用することは、バルクXORです）。もちろん、最後の数バイトには注意する必要があります。

于 2012-05-12T23:05:01.717 に答える
0

XOR は高速な操作であるため、アプリケーションは整数を生成できるレートによって制限されます。

それらが利用可能になったときにそれらをxorするだけでは、xor時間は方法に関係なく無視できます。

たとえば、テキスト ファイルから整数を読み取る場合。ディスク io + 解析時間は、xor 時間よりも数桁大きくなります。オペレーティング システムはread-ahead、実際には which を使用して、現在のバッチを処理している間に次の整数のバッチをフェッチすることを意味します。これは、解析 + xor によって、最後のバッチを除いて全体の処理時間に余分な時間が追加されないことを意味します。

于 2012-05-13T17:55:00.123 に答える
0

（あなたが言ったように）配列に対して a と呼ばれる要素をさらにxorする必要がある場合は、次の方法でこれを高速化できます。

int x = q[0]
for(int i = 1; i < q.Length; i++)
   x ^= q[i]

a1 ^= x
a2 ^= x
...

編集：申し訳ありませんが、基本的には逆です

int x = a1 ^ a2 ^ ... an
for(int i = 0; i < q.Length; i++)
     q[i] ^= x
于 2012-05-12T23:44:57.020 に答える