++wythern++

X presents Y for a better Z

2017年4月17日 #

ubuntu switch window in current workspace.

gsettings set org.gnome.shell.app-switcher current-workspace-only true

[ref]https://unix.stackexchange.com/questions/171964/restrict-alttab-to-the-current-workspace-in-gnome-3

posted @ 2017-04-17 10:21 wythern 阅读(2) | 评论 (0)编辑 收藏

2017年2月22日 #

Smb 连不上的一个可能

在公司整smb,用windows访问linux的share,但是配了很久都访问不了,一个选项一个选项的试,都不行。
偶尔发现一次能进到share folder,但是看起来windows一直在重新load该folder。
没有什么别的办法了,查日志:/var/log/samba/log.$ConnectionName.发现某个lib挂了。

[2017/02/22 17:16:29.389531,  0] ../source3/param/loadparm.c:4412(widelinks_warning)
  Share 'ubuntu-share' has wide links and unix extensions enabled. These parameters are incompatible. Wide links will be disabled for this share.
[2017/02/22 17:16:29.392626,  0] ../source3/lib/popt_common.c:68(popt_s3_talloc_log_fn)
  Bad talloc magic value - unknown value
[2017/02/22 17:16:29.392669,  0] ../source3/lib/util.c:789(smb_panic_s3)
  PANIC (pid 9408): Bad talloc magic value - unknown value
[2017/02/22 17:16:29.393497,  0] ../source3/lib/util.c:900(log_stack_trace)
  BACKTRACE: 28 stack frames:
   #0 /usr/lib/x86_64-linux-gnu/samba/libsmbregistry.so.0(log_stack_trace+0x1a) [0x7f21ca87514a]
   #1 /usr/lib/x86_64-linux-gnu/samba/libsmbregistry.so.0(smb_panic_s3+0x20) [0x7f21ca875220]
   #2 /usr/lib/x86_64-linux-gnu/libsamba-util.so.0(smb_panic+0x2f) [0x7f21cb5ec8df]
   #3 /usr/lib/x86_64-linux-gnu/libtalloc.so.2(_talloc_free+0x4de) [0x7f21c83742fe]
   #4 /usr/lib/x86_64-linux-gnu/libsamba-util.so.0(+0x1246c) [0x7f21cb5e346c]

看log好像是这个talloc lib和本地的smb lib 不match。
重装之 sudo apt-get install libtalloc2
搞定!
BTW: 本机的Samba的版本是Samba 4.3.9-Ubuntu。之前的talloc忘记看版本。。。无所谓了。

这里有人遇到一样的问题:https://answers.launchpad.net/ubuntu/+question/291448

posted @ 2017-02-22 09:46 wythern 阅读(12) | 评论 (0)编辑 收藏

2016年2月14日 #

【笔记】逆序数的求法

做个笔记!
【参考】http://blog.csdn.net/dlengong/article/details/7594919

3种思路:
1. 冒泡法统计交换次数。 O(N*N)
2. MergeSort同时统计。 O(NlogN)
3. 用binary index tree!。 O(NlogN),其实是基于IndexSort,然后用BinIdxTree求和。
   BIT适用的场景是:
   对于某个序列a0, a1, a2, ..., aN.
   BITsum(0, m) [0 <= m <= N] == sum(a0, a1, ..., am).
   和普通的sum不同点在于,当ai发生变化的时候,BIT支持在logN时间内重新算出sum值。
   所以这条求逆序的方式就是indexSort找到当前max value对应的idx, 然后a(idx) = 1,然后BITsum(0, idx)看看前面有多少1,就是当前value的逆序数K, sum(K)就得到了整个序列的逆序数。

posted @ 2016-02-14 21:27 wythern 阅读(40) | 评论 (0)编辑 收藏

2015年4月15日 #

[转]ACM学习大纲

希望自己能坚持学习,加油!


ACM学习大纲(转)

1 推荐题库

 

 http://ace.delos.com/usaco/

美国的OI 题库,如果是刚入门的新手,可以尝试先把它刷通,能够学到几乎全部的基础算法极其优化,全部的题解及标程还有题目翻译可以baidu 一个叫NOCOW 的网站。

 

 http://livearchive.onlinejudge.org/

上面有全部的赛区真题,绝大部分都可以提交,不适合当题库刷,不过在这里找题非常方便。

 

• http://poj.org/

不解释了,中国最知名的oj,题量非常之大,历史也很悠久,推荐刷一些代表性的题目。

 

 http://acm.timus.ru/
Ural 大学的oj,国外oj 中非常好的一个,题目非常锻炼基本功,管理员会不时添加一些新数据rejudge,
推荐找些通过人数适中的题目割一割。

 

转自http://www.cnblogs.com/Alandre/p/3383873.html#2954643

• http://acm.sgu.ru/

SGU 大学的oj,题目比较经典(比较老,几百年不更新了),不是特别推荐。

 

• http://www.spoj.pl
比较奇葩的一个oj,有一些与众不同的提交模式,也有很多著名的系列题目,qtree 等,题目质量很好,
但问题是国内的题解较少,新手如果只是想去割水题还是不要去了。

 

 http://acm.hdu.edu.cn
航电大学的oj,亮点是上面独有的中国多校联合训练的题目,而且有一版(貌似是20 开头的那版)水题
大全,新手提高很不错。

 

• http://acm.zju.edu.cn

每个月定时有月赛,浙大出题非常靠谱,推荐每个月月赛可以做一做。

 

• http://acm.hust.edu.cn
华中科技大学的oj,也就是各大oj 著名的virtual judge(三国五虎上将)的始作俑者,亮点就是那个模
拟比赛的功能异常好用,平时大家可以自己配题做做模拟比赛。

 

• http://www.codeforces.com
著名线上比赛网站,几乎每周都有一场线上比赛,有各国牛人参加,强烈推荐按时参加提高实力(要克
服时差问题)。

 

• http://www.topcoder.com/tc
更著名的一个线上比赛网站,历史相当悠久,而且有丰富的奖金,强烈推荐去做algorithm 比赛的single 
round match,非常提高智商。

 

2 算法总结及推荐题目

 

 

2.1 C++ STL

 

• STL 容器: set, map, vector, priority_queue, queue, stack, deque, bitset
• STL 算法: sort, unique, nth_element, reverse, rotate, next_permution, find, for_each, count, lower_bound,
max, swap, random_shuffle

 

2.2 基本算法

 

• 枚举: poj1753, poj2965, zoj1716, zoj3356, ural1010
• 贪心: poj1328, poj2109, poj2586, ural1303, sgu195, sgu171
• 递归与分治: ural1181, poj1579, poj1845, poj3714
• 构造: poj3922, poj1092, sgu121
• 模拟: poj3125, poj1068, poj2993, ural1007
• 排序: ural1082, poj2092, poj1694
• KMP 算法: poj2406
• 扩展KMP: poj3376, poj1699
• 二分法: poj1905, poj2002
• 三分法: hdu3400, hdu2298
• 矩阵乘法: zoj2105, zoj3289
• 离散化: ural1019, sgu177
• 快速傅立叶变换: poj2821

• 环状字符串最小表示: poj1509

 

2.3 图论

 

• 深度优先遍历: poj2488
• 宽度优先遍历: poj3620, poj2251
• 最短路: poj1847, poj1062
• 最小生成树: zoj1914
• 拓扑排序: zoj2193, zoj1060
• 二分图最大匹配: poj1469
• 二分图的最大权匹配: ural1076
• 稳定婚配问题: poj3487
• 最大流与最小割: poj1459
• 带下界的最大流: poj2396
• 最小费用最大流: poj2159
• 差分约束系统: poj1275
• 双连通分量: zoj2588
• 强连通分量: zoj2470, poj2186
• 割边及割点: poj3352, poj3177
• 度限制生成树: poj1638, hdu3070
• K 短路: poj2449, sgu145
• 最近公共祖先: poj1330
• 最优比率生成树: poj2728
• 次小生成树: poj1679
• 最小树形图: poj3164
• 欧拉回路与路径: poj1386, poj2337
• 哈密顿回路: sgu122
• 旅行商问题: poj2288
• 极大团搜索: poj2989
• 弦图的判定与应用: zoj1015

• 任意图的最大匹配: ural1099

 

2.4 数据结构

 

• 栈与队列: poj2559
• 并查集: poj1611, poj1182
• 哈希表: poj1840, poj1186
• 优先队列: poj1862, poj3253
• 可合并堆: zoj2334
• 字母树及AC 自动机: zoj3430, zoj3228
• 线段树: zoj3317, zoj1610
• 树状数组: poj2299, poj2352
• 倍增表(RMQ): poj3368, poj2452
• 平衡二叉树: poj2892, poj2418, poj3580
• 后缀数组: poj2774, poj3294
• KD 树: spoj2835, poj2528
• 树链剖分: poj3237, spoj2666, spoj2798
• 树的分治算法: poj2114, poj1987

• 动态树: hdu2475, hdu3601, hdu4010

 

2.5 搜索

 

• 简单技巧与剪枝: poj1033, poj3009
• 最优化与可行性剪枝: poj1011, poj1190
• 记忆化搜索: poj1191, poj1088
• 迭代加深: poj2286, poj2032
• A 搜索: hdu2467, poj1077
• Dancing Link: poj3074, hdu4069
• 折半搜索: zoj3631
• 双向广搜: poj1198, poj1915


2.6 动态规划

 

• 资源分配问题: poj3624, poj2063
• 区间划分问题: poj3280
• 状态压缩问题: poj1185
• 树形DP: poj1463, poj3345
• 数据结构优化DP: poj2374, poj2355
• 四边形不等式: poj1160
• 队列优化: zoj3399
• 插头表示的状态压缩DP: poj1739
• 最小表示法的状态压缩DP: spoj2159

• 数位DP: hdu3555, sgu258, sgu390

 

2.7 数学

 

• 排列组合: poj1850, poj3252
• Lucas 定理: poj3219
• 素数测试与筛法: poj2191, poj1811
• 大数分解的快速算法: poj1142
• 进位制: poj2798, poj1702
• 同余模运算: poj1006, poj2115
• 容斥原理: poj3904, poj1173
• 置换群与Burnside 引理: poj2888
• 递推关系与母函数: poj3734
• 高斯消元: poj1681, poj1222
• 概率与统计: poj2151, poj1021
• 扩展欧几里得算法: poj2891, poj1061
• 中国剩余定理: poj1006, zoj3538
• 离散对数与离散根: sgu261
• 拉格朗日插值: uva4209
• 迭代逼近: poj2868, poj3933
• 莫比乌斯反演: poj2154
• 博弈论与SG 函数: poj2960, poj2311
• 偏序论与格: poj1065, poj3636


2.8 计算几何

 

• 点积与叉积: zoj1010
• 线段相交: zoj1648
• 简单多边形的面积: poj1654
• 点到线段的最近最远距离: ural1348
• 凸包: poj1113
• 对锺点: poj2187
• 圆与点的切线: poj1375
• 圆与直线的交: poj1263
• 圆与圆的交: poj2564
• 圆与多边形的并与交: poj3675
• 点在多边形内: poj2398
• 半平面交: poj1474, poj2540
• 最小圆覆盖: zoj1450, spoj145
• 三维凸包: poj3528
• 三维点与直线的表示: poj3129

• 线性规划: poj1755

 

3 推荐书籍

 

• 《Introduction to Algorithms》
著名的算法大全,囊括全部的基础算法,其详尽程度超乎想象,而且都做了不同程度的扩展,若能同时
配合做一做上面的习题,受益匪浅。

 

• 《算法艺术与信息学竞赛》
俗称黑书,lrj 的成名之作,非常开拓视野,推荐阅读并掌握。另外,lrj 最近出了一本白书,我没读过,
听说更加基础,有兴趣的同学可以去读一读。

 

• 《Concrete Mathematics》
计算机学科的必备书籍之一,该书几乎包括计算机科学用到的全部数学知识,如果感兴趣,推荐深入阅
读更专业的书籍(组合数学、初等数论、离散数学、线性代数等等)。

 

• 《How to solve it》
这一本与上面基本不同,讲的是怎样解题,一本可以帮助你更好地数学建模抽象问题的书籍,不光对竞
赛,对整个思维方式都有帮助。

 

• 《Computational Geometry Algorithms and Applications》
相当详细的一本计算几何书籍,计算几何往往是一场比赛中最考研基本功最不需要思维复杂度的题目,
练好计算几何对比赛相当有利。

 

• 《C++ 程序设计思想与方法》
对C++ 语言特性不熟悉的同学建议看看,很好的一本介绍C++ 语言的书籍,有余力的建议再学个
java,写大模拟题、高精度题都有巨大优势。

 

• 全部的NOI 国家集训队作业以及论文
在网上全部可以找到,非常好的资料,都是历年的强手将当时最先进的知识整理所得,也包括不少题库的题解。

posted @ 2015-04-15 23:26 wythern 阅读(302) | 评论 (0)编辑 收藏

2014年6月23日 #

ubuntu 14.04 输入法快捷键

ubuntu 14.04 默认的输入法快捷键不在ibus里面修改,而是在keyboard setting里面,如图:
然后注销即可。

posted @ 2014-06-23 22:12 wythern 阅读(1800) | 评论 (0)编辑 收藏

2014年4月29日 #

安装signed apk时候遇到个问题[install_parse_failed_no_certificates]

APK是Eclipse export signed APK.本机可以正常安装,copy给别人安装提示错误:[install_parse_failed_no_certificates]。

正规办法应该是像这个帖子里面提到的:
http://www.vardhan-ds.co.in/2012/05/android-solution-install-parse-failed.html
StackOerflow里面也有不少回答。

后来是看到StackOverflow里面提掉有可能是 ~/.android/debug.keystore有问题导致,删除然后ADT会重新生成一个,然后再export出来的APK在别人的机器上就可以正常安装鸟~

posted @ 2014-04-29 18:24 wythern 阅读(1528) | 评论 (0)编辑 收藏

2014年4月16日 #

How to select the correct eglconfig.

REF: http://malideveloper.arm.com/develop-for-mali/sample-code/selecting-the-correct-eglconfig/

posted @ 2014-04-16 17:29 wythern 阅读(139) | 评论 (0)编辑 收藏

2013年12月26日 #

[转]Ftrace in Linux Kernel.

原文在这里
Ftrace in Linux kernel

posted @ 2013-12-26 10:45 wythern 阅读(216) | 评论 (0)编辑 收藏

2013年12月16日 #

Android Memory Profiling Summarize.

Profile Android App
http://www.cnblogs.com/fanfeng/p/3219751.html

Android application (performance and more) analysis tools - Tutorial
http://www.vogella.com/articles/AndroidTools/article.html#android_developersettings

android memory analysis.
http://stackoverflow.com/questions/3112671/android-memory-analysing-eclipse-memory-analyzer

Memory Analysis for Android Applications
http://android-developers.blogspot.com/2011/03/memory-analysis-for-android.html

TBD...

 

posted @ 2013-12-16 15:21 wythern 阅读(199) | 评论 (0)编辑 收藏

2013年11月4日 #

【转】Why your Android Apps Suck

Original Post is here.

Why I wrote this article?

When I learn more about Android’s graphics system, and do more work about how to use CPU/GPU in more paralleled way to improve the graphics performance in Android, I start to think that there are actually some big design mistakes in Android graphics system, especially the rendering architecture in the client side.

Some mistakes have been solved after 3.x, especially above 4.1, but others can never be solved due to the compatible reason. As developers, we need to know how the Android graphics system work, how to utilize the new features Android 3.x and 4.x provided, and how to do the optimazation and overcome the shortage of Android.

Direct Rendering

In the very beginning, Android’s client/server architecture of its graphics system choose the direct rendering mode, Android team develop a lightweight Window Compositor – SurfaceFlinger by themself, it response to create native windows, allocate graphics buffers and composite the window surface to display (via framebuffer). In client side, apps (through Android runtime) can use CPU to access the graphics buffer of native window directly (through Skia), or use GPU to manipulate it indirectly (through GLES). This direct rendeing mode is more appropriate than the traditional X in desktop Linux.

Window Composite in Server Side

SurfaceFlinger use GLES1 to do the window composition (via texture operation) in the very beginning, this cause two issues :

  • GPU may have more efficient way to do the window composition than use GLES;
  • When the client side also use GLES to render the window surface, it may competes with the server about the GPU resources;

Just mention, when GPU do not support GLES1, Android has a built-in SW version GLES1 stack, and it can use copybit HAL module provided by chip vendor to accelerated the texture operation.

So, after 3.0, Android introduce hwcomposer HAL module to solve these issues, also abandon the old copybit module. Chip vendor can through the implementation of hwcomposer module to declare they can do all of or part of windows’ composition by themselves, usually with dedicated hardware and always more efficient than use GLES. Also, after 4.1, hwcomposer can provide the vsync signal of the display, so that Android can sync three things together :

  • the windows composition in server side
  • the rendering of window surface in client side
  • the refresh of display

vsync

Rendering Architecture in Client Side

The most mistake Android team make is the rendering architecture of its GUI framework :

  1. It do not has a layer rendering architecture (or called scene graph in some GUI fw);
  2. It do not has a dedicated rendering thread to render the window surface;
  3. It’s rendering only use CPU until 3.0;

The first one is partially support after 3.0, the third is support after 3.0, but the second problem can never be solved…

Compare to iOS

In iOS, every View has a Layer as its backing store, app can create more Layers for better performance. View’s content will be drew into its Layer, as long as the content do not changed, the View do not need to draw itself again. iOS do a lot of things to avoid change the content of a View, many many properties of a View can be changed without affect to its content, such as background, border, opacity, position, transformation, even the geometry!!!

The composition of Layers done by another dedicated rendering thread, it always use GPU to draw each Layer to the window surface. The main thread only reponse to handle touch event, relayout the Views, draw View’s content into its Layer when necessary, etc… So the main thread only use CPU and the rendering thread use GPU mostly, and I think there will be just a few synchronization between these two threads, and they can run concurrently in most of time.

But in Android, the main thread need to do everything, such as handle touch events, relayout views, dequeue/enqueue graphics buffer, draw views’ content on window surface, and other things need to be done by app… And it only use CPU before 3.0!!! Even the position of a View just change one pixel, Android need to redraw its content along with the contents of other Views overlapped, and the content drawing is very expensive for CPU!!!

The Improvements

A lot improvements have been made after 3.0 to overcome the shortage of previous versions. Android 3.0 introduce a new hwui module, and it can use GPU to accelerated the drawing of View’s content, it create a hw accelerated Canvas to replace the old sw Canvas, the new Canvas use OpenGL ES as its backend instead of use SkCanvas from Skia.

Android 3.0 also introduce the DisplayList mechanism, DisplayList can be considered as a 2D drawing commands buffer, every View has its own DisplayList , and when its onDraw method called, all drawing commands issue through the input Canvas actually store into its own DisplayList. When every DisplayList are ready, Android will draw all the DisplayLists, it actually turn the 2D drawing commands into GLES commands to use GPU to render the window surface. So the rendering of View Hierarchy actually separated into two steps, generate View’s DisplayList, and then draw the DisplayLists, and the second one use GPU mostly.

When app invalidate a View, Android need to regenerate its DisplayList, but the overlapped View’s DisplayList can keep untouched.  Also, Android 4.1 introduce DisplayList properties, DisplayList now can has many properties such as opacity, transformation, etc…, and the changed of some properties of View will just cause changed of corresponding properties of its DisplayList and need not to regenerate it. These two improvements can save some times by avoid regenerate DisplayLists unnecessary.

Although Android can never has a layer rendering architecture, it actually introduce some Layer support after 3.0, a View can has a Layer as its backing store. The so called HW Layer actually back by a FBO, if the content of View is too complicated and unlikely to change in the future, use Layer may help. Also, when a View is animating (but content do not change), cache itself and its parent with Layers may also help. But use Layer with caution, because it increase the memory usage, if your want to use Layers during animation, your may need to release them when the animation is finish, Android 4.2 provide new animation API to help you about that. Also, because Android use GLES to draw the content of View, so most Views’ drawing will be fast enough, and the use of Layer may be unnecessary.

Android 4.0 also introduce a new type of native window – SurfaceTextureClient (back by a SurfaceTexture) and its Java wrapper TextureView, app can create and own this kind of native window and response to its composition. If the content of View is too complicated and continue to change, TextureView will be very helpful, app can use another thread to generate the content of TextureView and notify the main thread to update, and main thread can use the TextureView as a normal texture and draw it directly on the window of current Activity. (TextureView can also replace the usage of original SurfaceView and GLSurfaceView)

Android 4.1 make the touch event handling and ui drawing sync with the vsync signal of display, it also use triple buffers to avoid block the main thread too often because it need to wait the SurfaceFlinger to do the page flip and release the previous front buffer, and SurfaceFlinger will always sync with vsync signal of display.

The OpenGL Renderer for hw accelerated Canvas is continue be improved and become faster, especially for complicated shape drawing.

But…

But Android can never has a dedicated rendering thread… Although the drawing is much faster than before, and keep the changed of everything as little as possible during animating, it still need to share the 16ms interval with other jobs in main thread to achieve 60 fps.

So…

So, as developer, we need to utilize the improvements in higher version Android as much as possible :

  1. Turn on the GPU acceleration switch above Android 3.0;
  2. Use the new Animation Framework for your animation;
  3. Use Layer and TextureView when necessary;
  4. etc…

And avoid to block the main thread as much as possible, that means :

  1. If your handle the touch events too long, do it in another thread;
  2. If your need to load a file from sdcard or read data from database, do it in another thread;
  3. If your need to decode a bitmap, do it in another thread;
  4. If your View’s content is too complicated, use Layer, if it continue to change, use TextureView and generate its content in another thread;
  5. Even your can use another standalone window (such as SurfaceView) as a overlay and render it in another thread;
  6. etc…

Golden Rules for Butter Graphics

  • Whatever you can do in another thread, then do it in another thread;
  • Whatever you must do in main thread, then do it fast;
  • Always profiling, it is your most dear friend;

All you need to do is keep the loop of main thread under 16ms interval, and every frame will be perfect!

The Last Word

When I finish this article, what make me think most is, when you make a big design mistake in the very beginning, and you can not change it due to some reasons, no matter how hard you try to patch it in future, it will never get perfect again.

Android team make huge effects to provide features like Strict Mode, AsyncTask, Concurrent & Background GC, hw accelerated Canvas, hw Layer, TextureView, vsync, triple buffers, etc… All they do just about two things, do everything you can in another thread, and make the must thing in main thread faster, and these actually help a lot. But no matter how hard you try to use these features to improve your app, it is nearly impossible to get every frame perfect, because it is so hard to forecast everything the main thread will do in every loop, it may suddenly jump into something totally uncontrollable by you app and make you break the 16ms curse.

And the worse is, if you has a good design, you can continue improve it (like utilize more advance hardware), but the developer need not to know anything about this and do not need to change even one line of their code, if the app run on higher version OS with faster device, it just got the performance boost. If you has a bad design, although you do a lot of things to patch it, but the developer need to know why, they need to rewrite their code to use these new features, they need to know how to avoid the trap, they need to know how to make compatible with older version system, and many many other things…

This is too hard for a developer just want to build a useful and beauty app…

posted @ 2013-11-04 22:32 wythern 阅读(540) | 评论 (0)编辑 收藏

仅列出标题  下一页