V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
chaojie
V2EX  ›  问与答

穷举24位*800*600的图片,总共有多少张?

  •  
  •   chaojie · 2012-02-04 21:40:04 +08:00 · 7673 次点击
    这是一个创建于 4688 天前的主题,其中的信息可能已经有所发展或是发生改变。
    另外按你的算法,给定一个数字n,能否生成第n张图片。给定一张图片,能否算出其处在第几张?
    56 条回复    1970-01-01 08:00:00 +08:00
    Hooloowa
        1
    Hooloowa  
       2012-02-04 21:42:07 +08:00
    完全没有理解lz在说什么
    Livid
        2
    Livid  
    MOD
       2012-02-04 21:44:43 +08:00
    这是一个很有趣的想法。

    我好奇你是从哪得到这个灵感的?
    RanceR
        3
    RanceR  
       2012-02-04 21:52:11 +08:00
    算这个是要干什么...
    rechtar
        4
    rechtar  
       2012-02-04 21:52:12 +08:00
    In [15]: 800 * 600 * 2 ** 24
    Out[15]: 8053063680000L

    aoyoo
        5
    aoyoo  
       2012-02-04 21:52:25 +08:00
    一共是800*600*(2^24) 张 不是么?
    013231
        6
    013231  
       2012-02-04 21:59:55 +08:00
    总共2**(24*800*600)张吧?
    算第几张倒是简单.
    caomu
        7
    caomu  
       2012-02-04 22:02:20 +08:00
    想起大刘的《诗云》。。。
    reus
        8
    reus  
       2012-02-04 22:03:32 +08:00
    有2 ^ 24 ^ (800 * 600)张
    n转成图片,和十进制转16/32/64进制类似(看你机器字长选个效率最高的),连除取余,就是每一段的内容了。给图片算n就是逆运算。每16/32/64位乘以相应的权值然后相加
    reus
        9
    reus  
       2012-02-04 22:17:54 +08:00
    在内存里存这个图片,和存这个数字所用的空间是一样的,所以不能用来做图像压缩
    est
        10
    est  
       2012-02-04 22:26:38 +08:00
    @reus 这个应该是没有考虑到旋转和镜像的情况。嗯。
    chaojie
        11
    chaojie  
    OP
       2012-02-04 22:49:53 +08:00
    @013231 @rechtar @Livid 呵呵,做公交车想到的,这就大概把宇宙的所有情景给包含了吧。
    从2位2*2的结果来看,好像这算法不对
    rechtar
        12
    rechtar  
       2012-02-04 22:55:13 +08:00
    @chaojie 嗯,我直接把看到问题的第一反应贴上来了,无疑是错的见笑了
    Livid
        13
    Livid  
    MOD
       2012-02-04 22:58:37 +08:00
    @chaojie 是啊,太有意思了。

    如果能够有机器可以把这些图片存起来,再用算法过滤掉其中一些绝对无意义的。

    然后或许就可以在其中看到这个世界上可能会发生或是已经发生了的任何事情。
    rankjie
        14
    rankjie  
       2012-02-04 23:04:39 +08:00
    那也只是略大於肉眼可見範圍吧。。。
    chaojie
        15
    chaojie  
    OP
       2012-02-04 23:05:03 +08:00
    @Livid 我也是这样的想法,如果人们把存在的照片去比对其所在的位置,应该是有一定规律的。我觉得用这个规律应该可以过滤无意义的图片
    undeadking
        16
    undeadking  
       2012-02-04 23:06:15 +08:00
    这个数据量怎么感觉和26个字母全排列的数量级还要高…不存在那么强大的计算机吧
    chaojie
        17
    chaojie  
    OP
       2012-02-04 23:11:19 +08:00
    另外一个事,就是Dropbox之类的同步工具的数据为什么不存储在邮箱服务器呢?只要用户的文件能够通过Dropbox找到在哪个邮箱的哪个位置就行了啊。http的请求也可以用服务器代理到邮箱啊。
    我研究了两天这个事,突然觉得这事太简单,会不会又是我大脑短路想到的东西?

    android,nodejs的写了一下imap的,用qq邮箱,没什么技术难度啊。只是发现imap比pop3速度慢,不知是何缘故
    gfreezy
        18
    gfreezy  
       2012-02-04 23:16:31 +08:00
    @reus 在内存里寸800x600的24位图片不是只需要 800*600*24 bit 就够了吗
    chaojie
        19
    chaojie  
    OP
       2012-02-04 23:20:03 +08:00
    如果可以用123表示一张图片,这个压缩率也是无敌的高了
    Livid
        20
    Livid  
    MOD
       2012-02-04 23:20:20 +08:00
    24 位色不是指 24 种颜色,而是每个像素使用 24bit 来描述,红绿蓝各 8bit,所以,也就是说,单个像素的可能性是 256 ** 3。
    goldengrape
        21
    goldengrape  
       2012-02-04 23:24:20 +08:00
    hash+碰撞列表就可以吧。
    进一步,如果将画面之间的状态转移概率算出来,就是预言程序了。

    24位真彩有点过了,其实可以从初级的16位灰度,320*240开始。
    virushuo
        22
    virushuo  
       2012-02-04 23:29:27 +08:00
    @chaojie 这个是效率问题,而且dropbox对于文件并不看作一个整体,而是切成很多小块来同步。如果这样做效率就很低。

    其实你这个和图片,都是寻址方法吧,这个思路确实很有趣,很独特。图片这个仔细想想貌似能出现很有意思的东西。
    chaojie
        23
    chaojie  
    OP
       2012-02-04 23:35:43 +08:00
    @virushuo 但实际测试中下载速度稍有些问题,上传基本能达到宽带最高,当然是苦逼的1M的宽带,但不占用服务器的资源啊。空间相对来说很无限,自己还没成本,难道无限空间的诱惑抵不过一点效率的下降?
    goldengrape
        24
    goldengrape  
       2012-02-04 23:37:01 +08:00
    仅仅考虑16位灰度,单像素是2^8
    320*240的数据量是
    p=2^8^(320*240)=6.75... × 10^184952
    从一个状态转移到另一个状态的矩阵大小应该是p*p,
    也就是大约:4.55... × 10^369905
    这个数字好像有点大
    chaojie
        25
    chaojie  
    OP
       2012-02-04 23:39:57 +08:00
    @virushuo @Livid 图片如果真有这个算法,做图片压缩是最靠谱最简单的了,用一个数字表示一张图。其他很多有意思的应用就有点飘渺了,应该是物理学家数学家的范畴
    fanzeyi
        26
    fanzeyi  
       2012-02-04 23:40:38 +08:00
    曾经跟同学说过 每天用程序随机生成一副图片 有朝一日肯定会碰到一副名画的

    还有 这个想法来自于《失控》吧 有一章讲这个的 当时就是看这个的时候想到这个的..
    fanzeyi
        27
    fanzeyi  
       2012-02-04 23:41:13 +08:00
    但是 各位聪明的程序员们 在这之前你们要得到一个 真·随机数发生器 ..
    virushuo
        28
    virushuo  
       2012-02-04 23:41:30 +08:00
    @chaojie 这可不是一点效率下降了,尤其是有文件变化时候,会把涉及到的文件全都要比较,如果不是切小块hash的,任何一点点变化都会导致整个文件重传。

    跑题了,还是继续说图片吧。。。
    goldengrape
        29
    goldengrape  
       2012-02-04 23:43:34 +08:00
    考虑使用常规的图像压缩算法,比如余弦的那些系列。
    如果是完全随机的图片,是非常难以压缩的,而完全的色块,压缩比又非常之高。所以可以通过图像的可压缩率来判定图像是否又意义。相当于一个带通滤波器。

    如果考虑给定压缩算法的『带宽』,那么还可以把上述的可能性降低,甚至是降低很多。也许指数项就能降低几个数量级。
    Digi
        30
    Digi  
       2012-02-04 23:44:31 +08:00
    @caomu

    没错,和那个思路是一样的。按照《诗云》中的设想,不但重现过去历史上所有的诗歌,还会穷举出未来的名句

    KK 在《失控》中描述的博尔赫斯图书馆也是这样,算法蓬勃地生长进化,自行创造出前所未有的内容
    fanzeyi
        31
    fanzeyi  
       2012-02-04 23:45:08 +08:00
    http://www.boallen.com/random-numbers.html

    看看这个吧=.= 除非你真的能搞到一个 真·随机数发生器
    fanzeyi
        32
    fanzeyi  
       2012-02-04 23:45:32 +08:00
    @Digi 对就是那一章.
    chaojie
        33
    chaojie  
    OP
       2012-02-04 23:50:19 +08:00
    @goldengrape @reus @013231 你们的算法好像是一样的,我数学不好,不知道结果对不对。
    2位2*2结果应该是16,2^1^(2*2)确实是16,我只知道这,汗。。。。。。

    那么怎么根据n求图片,以及逆运算是什么呢?
    goldengrape
        34
    goldengrape  
       2012-02-04 23:52:20 +08:00
    @fanzeyi 关于真随机数 vs 伪随机数。从链接中的图片可以通过肉眼发现伪随机数的模式涌现。

    对于股票价格的波动,有效市场理论认为是随机波动(真随机数),其他理论认为不是(伪随机数)。那么是否有一种良好的呈现股票价格的方法能够使人眼清晰的感受到其中的模式?并用来预测股价?
    chaojie
        35
    chaojie  
    OP
       2012-02-04 23:55:13 +08:00
    @fanzeyi 还未看失控,其实我的世界观就是一切都是可能性。另外还有事物之间没有任何联系性。

    呵呵,当然这世界观只用来深信,从不使用
    goldengrape
        36
    goldengrape  
       2012-02-05 00:00:11 +08:00
    如果是穷举所有的股价和成交量呢?貌似复杂度一下子降低了很多。可统计的数据也有很多,状态转移的概率也是可能被计算的了。

    这比穷举整个世界来得容易,也更赚钱些
    chaojie
        37
    chaojie  
    OP
       2012-02-05 00:03:33 +08:00
    @virushuo 我还是决定做出来看有木有人使用,主要现在做其他的感觉很无力,转移下视线也好。没准结局会是把邮箱作为惰性空间使用,或是给我的Drop盒做备份也好,哈哈
    goldengrape
        38
    goldengrape  
       2012-02-05 00:22:40 +08:00
    股票的价格最小单位是0.01元。应该不会有超过1000元/股的股票。交易所每天9点到下午3点开市。
    于是穷举:
    (1000/0.01)^(60*60*6)=1*10^108000

    实际上大于100元的股票也不算多。那么
    (100/0.01)^(60^60^6)=1 × 10^86400

    再进一步,我只限定自己买卖10元价格区间内的股票,比如10-20元区间的。那么
    1 × 10^64800

    涨停跌停之类也许用个FFT的滤波器可以过滤。
    比如到了 1 × 10^6480 的数量级,是否可以建立完整的预测体系呢?当然,这个体系有如下问题:
    1. 是基于过去数据的,至少没有包含本模型的影响
    2. 要求的置信区间太高。
    virushuo
        39
    virushuo  
       2012-02-05 00:26:23 +08:00
    @goldengrape 我也觉得用来计算股票比较好玩。
    goldengrape
        40
    goldengrape  
       2012-02-05 00:35:20 +08:00
    如果只考虑10元区间内,15分钟采样一次,那么数据量是10^72,大概已经是个可处理的范围内了。
    然后统计出过去所有股票交易时间内这些交易图像的转移概率,
    比如你今天12点看到了一支股票价格的波动符合第3,4,7,9号图,有>90%的概率变成第3,4,5,6,7,8,9号图。。。
    reus
        41
    reus  
       2012-02-05 00:51:25 +08:00 via iPhone
    @gfreezy 是的,所以有2 ^ (24 * 800 * 600)种可能。这段内存可以看作是一个图片,也可以看作是一个整数。图片或者整数,只是人类赋予这些0101的意义,对计算机来说却没有区别
    chaojie
        42
    chaojie  
    OP
       2012-02-05 01:13:03 +08:00
    @reus 汗,没看到,原来压缩早就被否认了。。。无知了
    reus
        43
    reus  
       2012-02-05 01:13:20 +08:00 via iPhone
    @gfreezy 是的,所以有2 ^ (24 * 800 * 600)种可能。这段内存可以看作是一个图片,也可以看作是一个整数。图片或者整数,只是人类赋予这些0101的意义,对计算机来说却没有区别
    dreamersdw
        44
    dreamersdw  
       2012-02-05 01:18:02 +08:00
    1. 所有可能的图片一共有 (2^24)^(800*600) = 3.549 x 10^3467865 张
    2. 可以。比如想生成第 13 张图片,可以把 13 用二进制表示成 1101,然后再将数字逆序排得到1011,最后补全 479996 个 0,就得到了那张图片的二进制表示。
    3. 可以。将图片二进制数据逆序排列,可视其为一个巨大的二进制数,也就图片所在的位置。

    但考虑到宇宙中可观测的原子数量只有 10^80 个,我们永远不可能枚举出所有的图片。想用序号代替原始图片,以取代目前的压缩算法也是不现实的。虽然第 0 张图片只需要占用 1 个比特,但最后一张图片,却要占用 2^(800*600) 个比特。再说,既然我们都能从序号推断出图片内容了,序号中包含的信息一点也不会比图片本身的信息少。

    3.549 x 10^3467865 张图片一定会包含很多信息吧。不,只包含了很少的信息。因为只需要写一个非常短的程序就可以生成所有的它们。信息是可以帮助消除不确定性的东西。可把所有生成的图片都放在你面前也不能帮助你消除多少不确定性。
    chaojie
        45
    chaojie  
    OP
       2012-02-05 01:28:21 +08:00
    @reus 原来在#8就已经完全解决这个问题,只是说的太简单,我一下没看懂。如果16进制,也就是说从全0,到全F,000000.....000000 到 FFFFFF......FFFFFF,每6位作为一个像素颜色,共有800*600个像素,所有这些数字就代表所有的可能性。虽然不能用来压缩,但应该还是很有意义的

    我这样理解对吧?大学只学经济数学的悲惨路过
    013231
        46
    013231  
       2012-02-05 01:29:59 +08:00
    其实吧, 想要用序号表示任意信息, 计算pi(圆周率)就可以了. pi中包含了任意有限长的数字序列.
    http://www.matrix67.com/blog/archives/397
    chaojie
        47
    chaojie  
    OP
       2012-02-05 01:30:13 +08:00
    @dreamersdw 刚明白过来发出去就又看到了你的详细解释
    vmebeh
        48
    vmebeh  
       2012-02-05 01:42:01 +08:00
    @dreamersdw 序号只是一维, 图片至少是个单色的二维.
    reus
        49
    reus  
       2012-02-05 02:03:10 +08:00 via iPhone
    @chaojie 嗯,就是说图片和对应的数字,在计算机中的表示是一模一样的(也可以不同,像dreamersdw的算法就是不同的),所以“转换”这个操作,电脑是不需要工作的,转换的只是你解释这一坨0101的方式,也就是你赋予它的意义,也就是,你说它是数字它就是数字,说它是图片就是图片,甚至说它是程序,是视频,是音频都可以
    所以其实我是觉得这个没啥意义的(……)
    dreamersdw
        50
    dreamersdw  
       2012-02-05 02:06:16 +08:00
    修正前面一个错误,按序号排列的话,最后一张图片的序号本身占用的空间是 24*800*600 比特。
    X_Del
        51
    X_Del  
       2012-02-05 07:27:16 +08:00
    问题在于:将世界上所有照片压缩成这个大小,等超过这个数时,一定有人抄袭了……
    ro00
        52
    ro00  
       2012-02-05 10:50:50 +08:00
    这样的话你相当与拥有了在这个数据大小范围内的一切数据,不止是图片,可能是文本,程序,声音....
    当然这个里面很多情况下是没有什么意义的
    mjar
        53
    mjar  
       2012-02-05 11:57:03 +08:00
    !!看了两遍,明白了是个很帅的想法。
    Platinum
        54
    Platinum  
       2012-02-05 13:41:45 +08:00
    不用算也知道这个数奇大,大到大部分人无法理解的程度

    如果大家都能理解这个数,那这个话题基本不会有什么讨论

    其实第 n 张图片,这序号 n 就是图片的完整信息,只不过是把这个数看成一个 800x600图片 binary 还是 unsigned integer 序号的问题
    tiantian20007
        55
    tiantian20007  
       2012-02-07 07:46:37 +08:00
    @caomu 果然处处是同类。大爱《诗云》,那简直是浪漫到极致的科幻。同样的结局:要实现一个程序,能把其中绝大多数无意义的画过滤掉,选出所谓的名作,比把所有的图片穷举出来还难得多。
    diamondtin
        56
    diamondtin  
       2012-02-08 16:46:42 +08:00
    我觉得这个问题和『无限猴子定理』(http://zh.wikipedia.org/wiki/%E7%84%A1%E9%99%90%E7%8C%B4%E5%AD%90%E5%AE%9A%E7%90%86) 很相似,那个定理讨论的是概率,无穷小概率时间还是有“可能”发生。
    虽然24位800x600的图片看似不大,不过这个数实际是天文数字,实际上不可能。

    但是关于索引这些图片倒是比想象中靠谱一些。因为24位800x600图片对应的全部可能正好可以映射到它对应的二进制序列上面应该是1406KB,由于这个空间是密集的,所以这1406KB就可以作为这张图片的唯一编号。那么给定一个照片的二进制表示那么这张照片的编号也就知道了。

    不知道我这洋相是否对。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1366 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:57 · PVG 01:57 · LAX 09:57 · JFK 12:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.