Skip to content

Instantly share code, notes, and snippets.

@tokoroten
Created May 25, 2013 12:39
Show Gist options
  • Save tokoroten/5648940 to your computer and use it in GitHub Desktop.
Save tokoroten/5648940 to your computer and use it in GitHub Desktop.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Security.Cryptography;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static ushort getindex(ulong index)
{
ulong r = index % 10;
ulong q = index / 10;
byte[] s = Encoding.ASCII.GetBytes(q.ToString());
SHA1 h = new SHA1CryptoServiceProvider();
var d = h.ComputeHash(s);
ushort result = (ushort)(d[2 * r] << 8 | d[2 * r + 1]);
return result;
}
static ushort[] getindex_array(ulong index)
{
byte[] s = Encoding.ASCII.GetBytes(index.ToString());
SHA1 h = new SHA1CryptoServiceProvider();
var d = h.ComputeHash(s);
ushort[] result = new ushort[10];
for (var i = 0; i < 10; i++) {
result[i] = (ushort)(d[2 * i] << 8 | d[2 * i + 1]);
}
return result;
}
static ulong getsign(ulong count, ulong skip)
{
var sorted = new List<ushort>();
for(var i = 0UL ; i < count; i++)
{
sorted.Add(getindex(i));
}
sorted.Sort();
ulong total = 0UL;
for(var i =0UL; i < count; i+=skip)
{
total += (ulong)(sorted[(int)(i)]);
}
return total;
}
static ulong[] get_bucket(ulong index)
{
var bucket = new ulong[0x10000];
var loop_num = index/10;
for (var i = 0UL; i < loop_num; i += 1) {
var hash = getindex_array(i);
foreach(var item in hash){
bucket[item] += 1;
}
}
return bucket;
}
static ulong[] get_bucket2(ulong index)
{
var bucket = new ulong[0x10000];
var loop_num = index / 10;
SHA1 h = new SHA1CryptoServiceProvider();
for (var i = 0UL; i < loop_num; i += 1)
{
byte[] s = Encoding.ASCII.GetBytes(i.ToString());
var d = h.ComputeHash(s);
for (var j = 0; j < 10; j++)
{
int bucket_index = (d[2 * j] << 8 | d[2 * j + 1]);
bucket[bucket_index] += 1;
}
}
return bucket;
}
static ulong[] get_bucket3(ulong index)
{
var parallel_num = 16UL;
var bucket = new ulong[parallel_num, 0x10000];
if (index < 1000){
return get_bucket2(index);
}
//Thread.CurrentThread.Priority = System.Threading.ThreadPriority.Highest; //追加
var options = new ParallelOptions();
//options.MaxDegreeOfParallelism = 4;
options.MaxDegreeOfParallelism = (int)parallel_num;
Parallel.For(0, (int)parallel_num, options, thread_id =>
{
ulong start = (ulong)((index / 10UL * (ulong)(thread_id)) / parallel_num);
ulong end = (ulong)((index / 10UL * (ulong)(thread_id + 1)) / parallel_num);
SHA1 h = new SHA1CryptoServiceProvider();
//var h = new SHA1Managed();
for (var i = start; i < end; i++)
{
byte[] s = Encoding.ASCII.GetBytes(i.ToString());
var d = h.ComputeHash(s);
for (var j = 0; j < 10; j++)
{
int bucket_index = (d[2 * j] << 8 | d[2 * j + 1]);
bucket[thread_id, bucket_index]++;
}
}
Console.WriteLine("Thread" + thread_id + "finished " + start + " " + end);
});
var result_bucket = new ulong[0x10000];
for(var i = 0 ;i < 0x10000; i++){
for(var thread_id = 0; thread_id < (int)parallel_num; thread_id++){
result_bucket[i] += bucket[thread_id, i];
}
}
return result_bucket;
}
static ulong[] get_bucket_dummy(ulong index)
{
var bucket = new ulong[0x10000];
for (var i = 0; i < 0x10000; i++)
{
bucket[i] = index >> 16;
}
return bucket;
}
static ulong getsign_with_bucket(ulong count, ulong skip)
{
if (count % 10 != 0) {
return 0;
}
//var bucket = get_bucket(count);
//var bucket = get_bucket2(count);
var bucket = get_bucket3(count);
//var bucket = get_bucket_dummy(count);
var loop_num = count / skip;
var total = 0UL;
var i = 0;
for(var k = 0UL; k < loop_num; k++){
while(true){
if(bucket[i] > 0){
total += (ulong)(i);
break;
}else{
i+=1;
}
}
var left = skip;
while(left > 0){
while(bucket[i] > 0){
if (bucket[i] >= left)
{
bucket[i] -= (left);
left = 0;
}
else{
left -= bucket[i];
bucket[i] = 0;
i+=1;
}
if (left == 0)
{
break;
}
}
if (bucket[i] == 0){
i += 1;
}
}
}
Console.WriteLine(total);
return total;
}
static TimeSpan print_sw(Stopwatch sw) {
sw.Stop();
TimeSpan ts = sw.Elapsed;
Console.WriteLine(ts);
sw.Reset();
sw.Start();
return ts;
}
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
var write_stream = new System.IO.StreamWriter("./result.txt");
print_sw(sw);
/*
write_stream.WriteLine(getindex(0));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getindex(123456));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign(100, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(100, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(1000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(10000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(100000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(1000000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(10000000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(100000000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(1000000000, 10));
write_stream.WriteLine(print_sw(sw));
write_stream.WriteLine(getsign_with_bucket(10000000000, 10));
write_stream.WriteLine(print_sw(sw));
//*/
write_stream.WriteLine(getsign_with_bucket(107374182400, 16777216));
write_stream.WriteLine(print_sw(sw));
write_stream.Flush();
Console.ReadLine();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment