Intel的Optane真的很NB吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Hardware - 计算机硬件

Intel的Optane真的很NB吗？

Intel的Optane真的很NB吗？# Hardware - 计算机硬件

m*q2017-03-27 07:03

1 楼

Finding a duplicated integer. Given a read-only array of n integers between
1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use
only O(1) space. Hint: equivalent to finding a loop in a singly linked
structure.
看了提示好像更糊涂了
read-only array, O(n) time and O(1) space,而且不限定只有一个interger
missing，貌似没办法啊..

G*Y2017-03-27 07:03

2 楼

那不是硬件商谷又要焕发第二春了？

d*y2017-03-27 07:03

3 楼

可以把数组元素的值看着指标。
这样就像链表了。
不过觉得也不能O(n)。

k*02017-03-27 07:03

4 楼

据说很牛，但价钱也很牛，要普及得等

f*t2017-03-27 07:03

5 楼

“Hint: equivalent to finding a loop in a singly linked
structure.”
弄两个index，一个每次前进1，另一个前进2的办法？不像是O(n)时间内的算法

d*32017-03-27 07:03

6 楼

benchmark出来就知道了，不过感觉作为ssd的cache，就算benchmark很牛，实际效果也
很有限。

s*x2017-03-27 07:03

7 楼

This is exactly equivalent to finding loop in a singly linked list.
The singly linked list is defined with entry A[0] of the input array as the
HEAD node, and the numeric value of each array element as the array index
for the NEXT node. Since every array element A[i] is between 1..(n-1), all
the nodes have valid NEXT node pointers. Thus by sequentially traversing the
list you will encounter a loop.
Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
while (I1 != I2), let I1 = A[I1] and I2 = A[A[I2]] for each iteration. This
is O(n) because the loop contains no more than n elements.

j*f2017-03-27 07:03

8 楼

看性能参数很一般啊？速度比好的ssd差好多

【在 G**Y 的大作中提到】

: 那不是硬件商谷又要焕发第二春了？

r*g2017-03-27 07:03

9 楼

真牛，太巧妙了，关键是如何和这个题目联系起来，佩服佩服。
咋一看觉得区别很大，稍微画一下确实如此。

the
the
This

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

: This is exactly equivalent to finding loop in a singly linked list.
: The singly linked list is defined with entry A[0] of the input array as the
: HEAD node, and the numeric value of each array element as the array index
: for the NEXT node. Since every array element A[i] is between 1..(n-1), all
: the nodes have valid NEXT node pointers. Thus by sequentially traversing the
: list you will encounter a loop.
: Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
: while (I1 != I2), let I1 = A[I1] and I2 = A[A[I2]] for each iteration. This
: is O(n) because the loop contains no more than n elements.

d*e2017-03-27 07:03

10 楼

已经有人指责牙膏夸大，糊弄吃瓜群众：
http://semiaccurate.com/2017/03/27/intel-crosses-unacceptable-ethical-line/

【在 G**Y 的大作中提到】

: 那不是硬件商谷又要焕发第二春了？

s*x2017-03-27 07:03

11 楼

But wait a minute, this is still not completely solved. If only given O(1)
space, then you can't easily backtrack. When you encounter the loop, how do
you go back to find the place where two nodes point to the same node?

G*Y2017-03-27 07:03

12 楼

这东西不就是一个mlc的ssd吗？
反正我是一直没搞明白

【在 j***f 的大作中提到】

: 看性能参数很一般啊？速度比好的ssd差好多

c*t2017-03-27 07:03

13 楼

http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#

do

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

: But wait a minute, this is still not completely solved. If only given O(1)
: space, then you can't easily backtrack. When you encounter the loop, how do
: you go back to find the place where two nodes point to the same node?

c*j2017-03-27 07:03

14 楼

求大牛指正，
这个为什么不能求和 sum1
减去等差数列的和 sum2，因为1 to n-1
sum1-sum2 is the duplicated number?

y*g2017-03-27 07:03

15 楼

没说只有一个重复。
可能有多个重复

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

: 求大牛指正，
: 这个为什么不能求和 sum1
: 减去等差数列的和 sum2，因为1 to n-1
: sum1-sum2 is the duplicated number?

c*j2017-03-27 07:03

16 楼

不是
of *n* integers between 1 and *n-1*
e.g 100 个数 between 1-99？
不过确实不是太清楚

m*i2017-03-27 07:03

17 楼

check cycle的方法，不对吧
如果
array 1 2 3 3 4
index 1 2 3 4 5
第一个就infinite loop了

q*92017-03-27 07:03

18 楼

between
Is the array sorted?

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

: Finding a duplicated integer. Given a read-only array of n integers between
: 1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use
: only O(1) space. Hint: equivalent to finding a loop in a singly linked
: structure.
: 看了提示好像更糊涂了
: read-only array, O(n) time and O(1) space,而且不限定只有一个interger
: missing，貌似没办法啊..

m*q2017-03-27 07:03

19 楼

题目中说明了，index是 0~n-1,value是1~n-1，
所以a[0]的值一定在1~n-1,你说的情况不会出现。
不过这是这道题的一个很强的限制条件。如果value
的范围是0~n-1，那么检查cycle的方法不能用于
解这题，因为会有local cycle的情况，无法保证
找到cycle，就像你说的
index 0 1 2 3 4
value 4 2 2 3 0
dup是2，但是check cycle只能检查到0，4构成的环，
无法找到2这个dup。只是这道题目对取值的限制
保证了这种情况不会发生。

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

: check cycle的方法，不对吧
: 如果
: array 1 2 3 3 4
: index 1 2 3 4 5
: 第一个就infinite loop了

C*l2017-03-27 07:03

20 楼

如果是sorted的就很好做。找邻居就行了。不是sorted的话就真的不知怎样才能O(1)
space了。

a*62017-03-27 07:03

21 楼

Suppose the array is A[1]... A[n], and each A[i] \in {1, ..., n-1}
Corrected method:
1. Start from A[n] instead of A[1]
2. Once I1 == I2, use another O(N) time to find the length of the cycle
3. Then start from A[n] again: set I1 = n and I2 = A[A[A[A[I1]]]] (if the
cycle's length is 4); repeat I1 = A[I1] and I2 = A[I2] until I1 == I2

the
the
This

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

e*s2017-03-27 07:03

22 楼

应该就是150题的2.5吧。中间有个TRICK，meet point在K STEP BEFORE LOOP START
所以当n1, n2相遇，把n1放回数组头，在一人走一步，再次相遇就是dup了