V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
chaoxu
V2EX  ›  奇思妙想

一个算法问题的数据库的想法

  •  
  •   chaoxu · 2019-02-08 02:51:56 +08:00 · 2830 次点击
    这是一个创建于 2117 天前的主题,其中的信息可能已经有所发展或是发生改变。

    两个数据. 问题和算法(包括数据结构) 问题是规定的 input 和 output 的. (数据结构类问题稍微复杂一点) 每个算法都是解决一个特定问题的.

    • 问题图: 对于 B 问题的 input 的 restriction 获得问题 A, 则 A 是 B 的特例, 则 B 的算法都能用在 A 上. 问题之间的特例关系是个有向无环图.
    • 问题 x 算法图:
      • 问题->算法: 每个问题, 有些解决它的算法.
      • 算法->问题: 算法的里面有 subroutine, 是解决个问题的 oracle.
      • 问题 x 算法图: 建立在上面的有向二分图. 这个图上, 是可能有环的.

    几大重要功能

    1. 特例的 inheritance. 难度 ★ : 比如问题 A 里, 有个特例是 B. 这里录入 B 的时候只需要说 inherit A. 然后只需要增加不一样的东西. 这样原先可以使用在 A 的算法现在还能使用在 B. 是的这非常 OO.

    2. 自动计算复杂度. 难度 ★★ : 比如 一个解决问题 A 的一个算法其中要跑解决问题 B 的算法 n 次. 而跑的时候给 B 的算法的 input 的大小是 n^2. 则这个算法的时间复杂度是 O(n T(n^2)), T(n)是 input 大小为 n 的时候 B 要跑的时间. 显示真实时间的时候可以从数据库里, 找到所有 B 问题的算法, 每一个时间复杂度塞进去, 然后求 min. 好处是哪一天某个问题获得了新算法, 可以自动更新其他问题最快的算法.

    3. 时间复杂度排序. 难度 ★★★★★

      • asymptotic analysis. 比如计算出了 O(m^2)和 O(m)的算法, 哪一个快可以自动的获得. 而不用现在手动的去计算究竟哪个更快. 这个暂时可以用 SAGE 的 asymptotic expansion 功能. 它们应该足够好能自动化大多 comparison 了.
      • 更高级的分析. 比如可以加上约束, 如 m = O(n^2)这样的约束.
    4 条回复    2019-02-08 09:50:41 +08:00
    lrxiao
        1
    lrxiao  
       2019-02-08 03:06:37 +08:00
    感觉要定义一个问题和算法以及适用范围可能会比较困难,同时算法 /数据结构真的会有大量的通用结构吗?
    最近的 Morning Paper blog 好像有几篇自动选择算法数据结构的
    比如 https://blog.acolyer.org/2019/01/23/the-data-calculator-data-structure-design-and-cost-synthesis-from-first-principles-and-learned-cost-models/
    aijam
        2
    aijam  
       2019-02-08 03:25:10 +08:00
    于是 lz 发明了一种可以解决所有(大多数)问题的算法。。。
    chaoxu
        3
    chaoxu  
    OP
       2019-02-08 04:17:34 +08:00
    @lrxiao
    这里考虑的是类似算法讨论书籍里的那种问题.
    就是每个问题有明确的定义. input, output.
    在研究中, 算法调用解决其他问题的算法这还是非常常见的.
    momocraft
        4
    momocraft  
       2019-02-08 09:50:41 +08:00
    难点:算法的形式化描述

    另外 2 得到的可能只是一个复杂度上界
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4025 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 05:12 · PVG 13:12 · LAX 21:12 · JFK 00:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.