特别记录 Global Times 2016.10.12 【记录历史】谁重复验证了NgAgo？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

特别记录 Global Times 2016.10.12 【记录历史】谁重复验证了NgAgo？

特别记录 Global Times 2016.10.12 【记录历史】谁重复验证了NgAgo？# Biology - 生物学

w*o2016-10-12 07:10

1 楼

荷兰国旗的问题在：
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
谁有好的想法？
好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
谢谢！

b*32016-10-12 07:10

2 楼

perm 2月下旬批的，到现在140都还没交，两个月了，正常吗？

c*n2016-10-12 07:10

3 楼

特别记录
Date：2016年10月12日
Title：Scholars call for probe into NgAgo claims
Link：
http://www.globaltimes.cn/content/1010811.shtml
Key points：
1. Global Times article
2. twitter link:
https://twitter.com/globaltimesnews/status/786179634400468992
原文引用
“In August, Han had told the Global Times that foreign scientists'
accusations reveal their motive of ganging up against NgAgo. He had also
expressed his willingness to share his raw data and testing conditions.
Facing the doubts, the HUST told Xinhua in August that Han would "publicly
verify" his findings under the supervision of an "authoritative third party"
in a month, but no follow-up has been announced yet.
Han and the university could not be reached for comment as of press time.”

i*e2016-10-12 07:10

4 楼

这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
话我可以贴出我之前写过的代码。

F*u2016-10-12 07:10

5 楼

PERM有180天有效期
140不着急其实
不过还是盯着点

【在 b*******3 的大作中提到】

: perm 2月下旬批的，到现在140都还没交，两个月了，正常吗？

c*p2016-10-12 07:10

6 楼

可以用一个数组维护各段的起始下标。
找unknown的元素归属时可以用二分法在下标数组中查找。
k色旗元素交换的时间复杂度严格讲应该是O(n*k*logk)，n较大时相当于O(n)

【在 w****o 的大作中提到】

: 荷兰国旗的问题在：
: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
: 这个问题可以扩展到多于3个颜色的问题。比如扩展到20种颜色，该如何解决？难道需
: 要20多个变量吗？如果简单的模仿3个颜色的解法，会显得很罗嗦。
: 谁有好的想法？
: 好像这个版上有人面试的时候被问到过20种颜色如何排序的问题？能不能谁给讲讲？
: 谢谢！

b*32016-10-12 07:10

7 楼

我是concurrent filing. 想早点递485。有点着急。
怎么盯？盯律师还是盯老板？

【在 F*********u 的大作中提到】

: PERM有180天有效期
: 140不着急其实
: 不过还是盯着点

c*p2016-10-12 07:10

8 楼

这种代码你都写过，膜拜。

【在 i**********e 的大作中提到】

: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。

EM2016-10-12 07:10

9 楼

concurrent filing那还等啥？赶快啊，别等日子倒退再吃后悔药

【在 b*******3 的大作中提到】

: 我是concurrent filing. 想早点递485。有点着急。
: 怎么盯？盯律师还是盯老板？

w*o2016-10-12 07:10

10 楼

你能贴出来的话，最好了。
谢谢啦！

【在 i**********e 的大作中提到】

: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。

b*32016-10-12 07:10

11 楼

我当然想早点交。材料一个月前就准备好交给律师了，但从此音信渺无，律师邮件不回
电话不接，不知什么情况。

【在 EM 的大作中提到】

: concurrent filing那还等啥？赶快啊，别等日子倒退再吃后悔药

i*e2016-10-12 07:10

12 楼

看了我很久以前写的，当时应该写得满头大汗，现在自己完全忘了，不过幸好有注释，
应该不难理解。（我当时是先写了排4个颜色的，然后扩展到k）
这个复杂度应该不是最优的，后边有个 for 循环应该可以优化。请大家看看给些意见
怎么优化，多谢指教。
// Dutch National Flag Problem (DNFP) generalized to k different set of
colors.
// k = {0, 1, 2, ..., k-1}
// pre-condition: n >= 0, k >= 2
void SortK(int A[], int n, int k) {
assert(n >= 0 && k >= 2);
int *mid = new int[k];
// init values to satisfy invariant below
for (int i = 0; i < k-1; i++)
mid[i] = 0;
mid[k-1] = n-1;
// invariant:
// 0 <= mid[0] <= mid[1] <= mid[2] <= ... <= mid[k-1] < n,
// A[0..mid[0]-1] = 0,
// A[mid[0]..mid[1]-1] = 1,
// A[mid[1]..mid[2]-1] = 2,
// ...
// A[mid[k-2]..mid[k-1]] = mixed colors,
// A[mid[k-1]+1..n-1] = k-1.
// the range of mixed colors is: [ mid[k-2] ... mid[k-1] ]
// the array is sorted when mid[k-2] > mid[k-1] (ie, no more mixed colors)
while (mid[k-2] <= mid[k-1]) {
if (A[mid[k-2]] == k-1) {
swap(A[mid[k-2]], A[mid[k-1]]);
mid[k-1]--;
} else if (A[mid[k-2]] == k-2) {
mid[k-2]++; // no swap needed, advance
} else {
int x = A[mid[k-2]];
swap(A[mid[k-2]], A[mid[x]]);
mid[x]++;
// for maintaining invariant: (mid[x+1], mid[x+2] ... mid[k-2]) >= mid
[x]
for (int i = x+1; i <= k-2; i++)
if (mid[i] < mid[x])
mid[i] = mid[x];
}
}
delete[] mid;
}

b*32016-10-12 07:10

13 楼

有么有先例公司给办了perm 但是不给办140的？

c*p2016-10-12 07:10

14 楼

void swap(int *a, int i, int j)
{
int tmp;
if(i == j)
return;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
void flags(int* a, int n, int k)
{
int ind[k];
int i,j;
int low, high;
int tmp, key;
low = k / 2 - 1;
high = low + 1;
//ind = malloc(k * sizeof(int));
for(i = 0; i < k; i++)
{
ind[i] = (i < high)? 0 : n - 1;
}
i = 0;
while(ind[low] != (ind[high] + 1))
{
key = i;
tmp = a[key];
if(tmp <= low)
{
for(j = low; j >= 0; j--)
{

swap(a, key, ind[j]);
if(tmp == j)
{
ind[j]++;
break;
}
else
{
key = ind[j];
ind[j]++;
}
}
i++;
}
else
{
for(j = high; j < n; j++)
{
swap(a, key, ind[j]);
if(tmp == j)
{
ind[j]--;
break;

}
else
{
key = ind[j];
ind[j]--;
}
}
}
}
}

【在 i**********e 的大作中提到】

: 看了我很久以前写的，当时应该写得满头大汗，现在自己完全忘了，不过幸好有注释，
: 应该不难理解。（我当时是先写了排4个颜色的，然后扩展到k）
: 这个复杂度应该不是最优的，后边有个 for 循环应该可以优化。请大家看看给些意见
: 怎么优化，多谢指教。
: // Dutch National Flag Problem (DNFP) generalized to k different set of
: colors.
: // k = {0, 1, 2, ..., k-1}
: // pre-condition: n >= 0, k >= 2
: void SortK(int A[], int n, int k) {
: assert(n >= 0 && k >= 2);

y*g2016-10-12 07:10

15 楼

没有，赶紧找律师，不行就赶紧换律师

【在 b*******3 的大作中提到】

: 有么有先例公司给办了perm 但是不给办140的？

q*x2016-10-12 07:10

16 楼

count sort不就行了。

【在 w****o 的大作中提到】

m*y2016-10-12 07:10

17 楼

你pd 啥时候现在就打算交485？

【在 b*******3 的大作中提到】

: 我是concurrent filing. 想早点递485。有点着急。
: 怎么盯？盯律师还是盯老板？

q*x2016-10-12 07:10

18 楼

count sort不就行了。

【在 w****o 的大作中提到】

b*32016-10-12 07:10

19 楼

我是老pd, 08年11月。估计这版上没有比我更早的pd了。

l*a2016-10-12 07:10

20 楼

显然不希望你用counting sort

【在 q****x 的大作中提到】

: count sort不就行了。

m*y2016-10-12 07:10

21 楼

够早。换过工作吧？那信骚扰 hr 和律师吧

【在 b*******3 的大作中提到】

: 我是老pd, 08年11月。估计这版上没有比我更早的pd了。

H*e2016-10-12 07:10

22 楼

counting sort的特例吗？
还有干吗要那么多指针啊，直接数一遍，记下012的个数，然后往数组里写就可以了。
当然了，这样要走两遍

【在 w****o 的大作中提到】

b*32016-10-12 07:10

23 楼

换过不止一次。

【在 m*********y 的大作中提到】

: 够早。换过工作吧？那信骚扰 hr 和律师吧

c*p2016-10-12 07:10

24 楼

这样需要额外的非常数空间吧。。。尤其是种类数量上升之后

【在 H***e 的大作中提到】

: counting sort的特例吗？
: 还有干吗要那么多指针啊，直接数一遍，记下012的个数，然后往数组里写就可以了。
: 当然了，这样要走两遍

f*e2016-10-12 07:10

25 楼

查查原因？
我的perm2月中旬批。140未file。
上周终于figure out原因，原来是我自己单位还没给律师140的支票---我确实没想到。
盯了一下，周5支票寄去给律师了。希望能尽快file。

【在 b*******3 的大作中提到】

: perm 2月下旬批的，到现在140都还没交，两个月了，正常吗？

i*e2016-10-12 07:10

26 楼

Good Job，看来你代码没有我写的那么复杂，能说下思路吗？

【在 c****p 的大作中提到】

: void swap(int *a, int i, int j)
: {
: int tmp;
: if(i == j)
: return;
: tmp = a[i];
: a[i] = a[j];
: a[j] = tmp;
: }
: void flags(int* a, int n, int k)

q*x2016-10-12 07:10

27 楼

不需要。不就是计数吗？当然如果有satellite就不行了。

【在 c****p 的大作中提到】

: 这样需要额外的非常数空间吧。。。尤其是种类数量上升之后

c*p2016-10-12 07:10

28 楼

参考了那个参考链接的思路，把数组分成三部分：low, unknown, high
low和high各分k/2种颜色
开一个大小为k的数组ind，ink[i]记录第i种颜色再新来一个元素时应该进入的位置。
比如{0 0 1 2 3 4 4 .......}, ind={2 3 4 5 7.....}
对于每个unknown内的元素，先看属于low还是high；
以low为例，根据ind数组的指示依次交换至该元素所在的部分为止，
并相应地更新ind数组。举个例子：
{0 0 0 1 1 2 2 2 3 3 1 .....}，ind = {3 5 8 10}
第一次交换：{0 0 0 1 1 2 2 2 1 3 3} ind = {3 5 8 11}
第二次交换：{0 0 0 1 1 1 2 2 2 3 3} ind = {3 5 9 11}
第三次：已经换进所在的颜色区，更新ind数组：ind = {3 6 9 11}。
一个元素的交换完成。

【在 i**********e 的大作中提到】

: Good Job，看来你代码没有我写的那么复杂，能说下思路吗？

c*p2016-10-12 07:10

29 楼

这样做速度应该是O(k*n)，
一个test case：
Original array with 28 elements in 17 types:
8 16 3 8 8 13 3 15 15 0 13 16 13 15 3 11 15 5 10 10 0 16 15 11 7 11 10 5
Sorted array with 28 elements in 17 types:
0 0 3 3 3 5 5 7 8 8 8 10 10 10 11 11 11 13 13 13 15 15 15 15 15 16 16 16

【在 c****p 的大作中提到】

: 参考了那个参考链接的思路，把数组分成三部分：low, unknown, high
: low和high各分k/2种颜色
: 开一个大小为k的数组ind，ink[i]记录第i种颜色再新来一个元素时应该进入的位置。
: 比如{0 0 1 2 3 4 4 .......}, ind={2 3 4 5 7.....}
: 对于每个unknown内的元素，先看属于low还是high；
: 以low为例，根据ind数组的指示依次交换至该元素所在的部分为止，
: 并相应地更新ind数组。举个例子：
: {0 0 0 1 1 2 2 2 3 3 1 .....}，ind = {3 5 8 10}
: 第一次交换：{0 0 0 1 1 2 2 2 1 3 3} ind = {3 5 8 11}
: 第二次交换：{0 0 0 1 1 1 2 2 2 3 3} ind = {3 5 9 11}

w*o2016-10-12 07:10

30 楼

我也自己写了一个。其实就是拿到一个值后，根据值得大小，判断应该把者个值放在哪
里，把真正的操作用代码给直接的描述出来。
具体用法：比如有个数组a[]，有4种颜色，数组大小为n,可以调用 DNF_K(a, 4, 0, n-
1)
// this is the code for k colors.
// the element values can be 0, 1, 2, ..., k-1
// partition[i] records the starting index for value i
// partition[0] does not matter, and should be always 0
// partition[k-1] denotes the lower index of unknown section
// h denotes the upper index of unknown section
// sections are :
// 0 1 2 3 ... unknown k-1
// complexity: O(n*k)
//
void DNF_K(int a[], int k, int lowest, int highest)
{
int i;
int h;
int j;
int cur_element;
int *partition;
partition = (int *)malloc(sizeof(int) * k);
for (i = 0; i < k ; i++) {
partition[i] = lowest;
}
h = highest;
while(partition[k-1] <= h)
{
if(a[partition[k-1]] == k - 1){
swap(&a[partition[k-1]], &a[h]);
h--;
} else {
cur_element = a[partition[k-1]];
// swap the first elements in two adjacent sections backward
// from the unknown section until the section for cur_
element+1
for (j = k - 2; j >= cur_element + 1; j--) {
// swap the first elements in two adjacent sections
swap(&a[partition[j]], &a[partition[j+1]]);
//adjust the index for the touched partition
partition[j+1]++;
}
//adjust the index for the section for cur_element + 1
partition[j+1]++;
}
}
free(partition);
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}

【在 i**********e 的大作中提到】

: 这个扩展到只对 k 种颜色进行排序非常繁琐，被问到的概率也不大。你要是有兴趣的
: 话我可以贴出我之前写过的代码。