TRASH A dynamic LC-trie and hash data structure

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.2143

传统Trie的优化。

  • path compression: 连续若干个只有一个孩子节点可以压成一个
  • LC(level compression):若某一节点下面第k层的子树都非空,那么中间的k-1层都可以省略,直接把第k层的2^k个子树都接到自身
    • 压缩原理:现代指针大小8byte远远大于char的大小
  • TRASH:在每个插入Trie的子串前面都加一个hash值,这样能在LC的基础上分布更均匀

某项目的思考

背景

一个影视作品管理系统,PHP based,要求有影片、国家、作者、语言等各种信息的CRUD。

之前犯下的问题及改进措施

主要问题

没有采用ORM

这是最大的失误。原因是由甲方现场指导建表,表名不规范,如r_video_language。同时没有Model,全部数据都是裸写。

ORM和完善的Model对开发效率非常重要,同时也避免了安全性问题。https://www.v2ex.com/t/288772

改进的措施是渐进式的:

  • 首先所有的裸SQL找了个QueryBuidler替换掉
  • 之后新的模块采用了RedBeanPHP

为什么采用RedBeanPHP:

  • 开发成本,不能指望让配置环境就配了两天的用上eloquent/doctrine等builder。不过另一方面来说,正是因为这个原因这个项目才会最开始用PHP开发吧,门槛是比较低
  • 之前没有使用框架
  • 灵活性高,但问题是link的name是钦定的,不能修改,加之现在的link表名不规范(有下划线),导致原生store都会出现问题,必须要hack掉表名检查。为什么不改表名?因为一堆旧代码的兼容性保持不了……

前端没管理好

隐式依赖太多,重用性低。

最好的方案当然是用上browsify那一套工具链……但是同理不要对新人装nodejs抱有太大希望……所以算下来不能服务端打包只能客户端处理依赖,所以require.js吧……

把用到的vue组件都写成了foo.js和foo.template, 然后foo.js中依赖:

define(['vue', 'text!foo.template'], function(Vue, template) {
    Vue.components('foo', {
      el: template
    });
});

用的时候直接require就行了

对数据量没有明确统计

做得差不多了告诉我有10^6级别的数据。。。那之前查询还’like %$q%’……

这样下来很多地方都要改,本来下拉框的地方要做成自动补全+lazy加载,性能问题先缩水成`like $q%’建索引顶着,顶不住了再上solr/elastic search之流

次要问题

没文档

不说了。。。

搬砖思考

最近在实验室维护一个很老的PHP项目。。。大致来说就是一个电影数据库,每一个电影有着复杂的关联关系:例如说可能与多个staff有关,每个staff信息保存在people表中,这个staff在不同影片中角色可能不同,所以就要有relation_person_video表……
然后之前的代码已经基本垮了……前端JQuery强行插入HTML字符串维护列表…… get/post的时候直接发送{tablename, field, constraint}……而且后端也没校验、裸写SQL…… 耦合度非常高,这样就很难维护了……

接手之后做了一些微小的工作:

  • 前端:使用Vue进行数据绑定,一下子去掉了200+行的代码,特别是列表现在变得很方便处理了:
    <div id="listContainer">
        <ul>
        <li v-for="item in items">{{item}}</li>
        </ul>
    </div>
    
    <script>
    var list = [];
    $(function() {
        new Vue({
            el: '#listContainer',
            data: {
                items: list
            }
        });
    });
    </script>

    之后就像正常数组一样操纵list对象就行了

  • 后端:由于历史遗留问题不能用ORM……暂时用QueryBuilder先顶着
  • 架构:MVVM,影片信息和前端交互时全部包装成VM JSON,转换和存取都在后端完成