小编fon*_*ons的帖子

设G(U u V,E)是加权有向二分图(即U和V是二分图的两组节点,E包含从U到V或从V到U的有向加权边).这是一个例子:

在这种情况下:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

定义: DirectionalMatching(我编写这个术语只是为了让事情变得更清晰):可以共享起点或终点顶点的有向边集.也就是说,如果U-> V和U' - > V'都属于DirectionalMatching,那么V/= U'和V'/ = U,但它可以是U = U'或V = V'.

我的问题:如何有效地找到如上定义的DirectionalMatching,用于最大化其边缘权重之和的二分方向加权图？

通过有效,我的意思是多项式复杂性或更快,我已经知道如何实现一个天真的蛮力方法.

在上面的示例中,最大加权DirectionalMatching是:{F-> A,C-> E,B-> D},值为13.

正式证明这个问题与图论中任何其他众所周知的问题的等价性也是有价值的.

谢谢!

注1: 此问题基于最大加权二分匹配_with_有向边,但具有额外的松弛,允许匹配中的边共享原点或目的地.由于这种放松有很大的不同,我创造了一个独立的问题.

注2:这是最大重量匹配.基数(存在多少条边)和匹配所覆盖的顶点数与正确的结果无关.只有最大重量才算重要.

注2:在我研究解决问题的过程中,我发现了这篇论文,我认为对其他人试图找到解决方案会有所帮助:边缘彩色多图中的交替周期和路径:一项调查

注3:如果有帮助,您还可以将图形视为等效的2边彩色无向二分多图.然后,问题公式将变为:找到没有颜色交替路径的边集或具有最大权重和的循环.

注4:我怀疑这个问题可能是NP难的,但我不是那种减少经验的人,所以我还没有成功证明这一点.

又一个例子:

想象一下你有

4个顶点: {u1, u2} {v1, v2}

4边: {u1->v1, u1->v2, u2->v1, v2->u2}

然后,不管他们的权重,u1->v2而v2->u2 …

我的问题:

1. 函数指针是否由C标准保证？
2. 如果(1)的答案是肯定的.是不是在不同的最终编译单元(例如主可执行文件和共享库)中获得指针的情况？
3. 动态加载器如何处理？(我可以考虑一些可能导致棘手问题的原因,所有这些都与PIC代码有关(例如,精灵中的GOT表和COFF使用的等效表格)).无论(1)和(2)如何,linux加载器似乎都能保证这一点.

这是一个例子.上面的问题归结为C是否保证main.c打印: "Function equality: 1"或者"Function equality: 0",在第一种情况下,动态加载器如何实现这一点.

common.h:

extern void * getc_main;
extern void * getc_shared;
void assign_getc_shared(); 

main.c:

#include <stdio.h>
#include "common.h"

int main()
{
  getc_main = (void*) getc;
  assign_getc_shared();
  printf("Function equality: %d\n", getc_main == getc_shared);
  return 0;
}

shared.c:

#include <stdio.h>
#include "common.h"

void assign_getc_shared()
{
   getc_shared = (void*) getc;
}

在Unix中,这将使用以下命令进行编译:

cc -shared -fPIC -o libshared.so shared.c
cc -o main main.c -L. -lshared

并执行:

LD_LIBRARY_PATH=. ./main

由于与此问题无关的一些模糊原因,我需要使用MAP_FIXED来获取靠近libc的文本部分存储在内存中的页面.

在阅读mmap(2)之前(我本来应该做的),如果我用MAP_FIXED调用mmap并且基地址与已经映射的区域重叠,那么我期望得到一个错误.

然而事实并非如此.例如,这是某些进程的/ proc/maps的一部分

7ffff7299000-7ffff744c000 r-xp 00000000 08:05 654098                     /lib/x86_64-linux-gnu/libc-2.15.so

其中,在进行以下mmap调用之后......

  mmap(0x7ffff731b000,
       getpagesize(),
       PROT_READ | PROT_WRITE | PROT_EXEC,
       MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED,
       0,
       0);

... 变成:

7ffff7299000-7ffff731b000 r-xp 00000000 08:05 654098                     /lib/x86_64-linux-gnu/libc-2.15.so
7ffff731b000-7ffff731c000 rwxp 00000000 00:00 0 
7ffff731c000-7ffff744c000 r-xp 00083000 08:05 654098                     /lib/x86_64-linux-gnu/libc-2.15.so

这意味着我用自己的页面覆盖了专用于libc的部分虚拟地址空间.显然不是我想要的......

在mmap(2)手册的MAP_FIXED部分,它清楚地说明:

如果addr和len指定的内存区域与任何现有映射的页面重叠,则将丢弃现有映射的重叠部分.

这解释了我所看到的,但我有几个问题:

1. 有没有办法检测某些东西是否已映射到某个地址？没有访问/ proc/maps？
2. 有没有办法在找到重叠页面的情况下强制mmap失败？

我正在编写多平台代码,需要使用指向setjmp/sigsetjmp的指针.通常情况就是如此简单

#include <setjmp.h>
void * sigsetjmp_p = sigsetjmp;

但是,ISO和POSIX声明setjmp/sigsetjmp可以定义为宏,事实上我的linux框就是这种情况.以下摘录自/usr/include/setjmp.h:

# define sigsetjmp(env, savemask)       __sigsetjmp (env, savemask)

问题是,由于我没有传递参数sigsetjmp,宏不会扩展,并且sigsetjmp在libc中没有定义普通符号.我希望能够使用一些宏"黑魔法"来提取"__sigsetjmp"名称,但到目前为止我已经失败了.

另一种选择是__sigsetjmp直接使用 ,但这意味着检查每个支持平台的扩展,我不想这样做(因此这个问题的原因).

PS:我讨厌宏.

注意:

我需要它的原因有点模糊,但为了简化它,我想说我想用它进行指针比较.

#include <setjmp.h>
int equals_sigsetjmp(void *p)
{
 void * sigsetjmp_p =  sigsetjmp;
 return p == sigsetjmp_p;
}

编辑:

是的是的.我知道我不应该指望指向sigsetjmp它,因为它甚至可能不是某些平台上的函数,但这并不能解决我的问题.

在实践中,我所知道的所有平台都将其作为一个功能实现.

我可以应对这样一个事实:在几年内,我遇到了一个sigsetjump不适合某个平台的案例.但我不想应对的是通过每个支持的平台并检查setjmp.h宏定义,这是我现在唯一的选择.

我很欣赏标准的参考,但我希望得到一个实际的答案而不是纯粹的答案.

一些序言

似乎 malloc、calloc、realloc 和 free 都在ld-linux.soand 中复制了libc.so。据我了解，这是由动态加载器完成的，用于在加载ld-linux.so之前处理内存管理libc.so并使其内存管理功能可用。但是，我对那些重复的符号有一些疑问：

这是一个非常简单的 C 程序调用 malloc 并退出：

#include <stdlib.h>

int main()
{
  void *p = malloc(8);
  return 0;
}

我在 x86_64 linux 机器中用 gcc 编译它并用 gdb 进行一些调试：

$ gcc -g -o main main.c
$ gdb ./main
(gdb) start
Temporary breakpoint 1 at 0x4004f8
Starting program: main 

Temporary breakpoint 1, 0x00000000004004f8 in main ()
(gdb) info symbol malloc
malloc in section .text of /lib64/ld-linux-x86-64.so.2
(gdb) b malloc
Breakpoint …

假设我想创建一个不可修改的链表(即它只能遍历,一旦最初创建就不能添加或删除节点).这可以通过以下方式轻松实现:

struct ListNode
{
  int value;
  ListNode* nextNode;
}

我的问题是......是否可以使用引用而不是指针？

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

我不确定它会提供任何性能提升,但是......编码时出现了这个问题,到目前为止我的回答是否定的,但我可能会遗漏一些东西.

原则上,没有什么可以阻止您使用引用,并构建列表元素,如下所示:

ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

但是有一个鸡和蛋的问题,因为它next也会强化其next元素在其创作时存在等等......

注意:我认为我的问题也可以应用于将列表定义为:

struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}

我一直在尝试HackerRank,其中问题通常需要将整数行读入数组(切片).

对于许多问题,我的解析代码最终比解决方案的算法更大.例如,Sherlock和Array就是这种情况

关于如何简洁地将空格分隔的整数行解析成切片的任何想法？fmt.Scanf不支持切片,使用时bufio我得到很长的解决方案.

一些要求:

• 您只能使用标准库.
• 解决方案应该简洁,越短越好.
• 不应跳过错误检查.我知道输入在HackerRank中有明确定义,你应该能够偷工减料,但请不要,这是不好的做法.
• 它应该是合理有效的.

注意: 解析器应该只使用一行而不是完整输入.

以下(非最佳)代码为特定子集生成大小为N的所有子集.

这段代码有效,但正如我所说,这是非常不理想的.使用中间列表来避免Set.insert的O(log(n))似乎没有帮助,因为后来将列表重新转换为Set的成本很高

任何人都可以建议如何优化代码？

import qualified Data.Set as Set


subsetsOfSizeN :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
subsetsOfSizeN n s
  | Set.size s < n || n < 0 = error "subsetOfSizeN: wrong parameters"
  | otherwise = doSubsetsOfSizeN n s
 where doSubsetsOfSizeN n s
        | n == 0 = Set.singleton Set.empty
        | Set.size s == n = Set.singleton s
        | otherwise =
           case Set.minView s of
             Nothing -> Set.empty
             Just (firstS, restS) ->
               let partialN n …

我很惊讶地发现gcc强制代码与位置无关,即使命令行中没有明确提供这样的标志.

我怀疑它可能与Android动态加载器的某些期望有关(例如对重定位类型的期望以及将代码放在任何地方的自由)但我不确定.

任何人都能解释为什么会这样吗？

$ arm-linux-androideabi-gcc --version | grep GCC
arm-linux-androideabi-gcc (GCC) 4.4.3

$ arm-linux-androideabi-gcc -v -S main.c |& grep fpic
 /home1/local64/android-toolchain/bin/../libexec/gcc/arm-linux-androideabi/4.4.3/cc1 -quiet -v -iprefix /home1/local64/android-toolchain/bin/../lib/gcc/arm-linux-androideabi/4.4.3/ -isysroot /home1/local64/android-toolchain/bin/../sysroot main.c -mbionic -fpic -quiet -dumpbase main.c -march=armv5te -mfloat-abi=soft -mfpu=vfp -auxbase main -version -o main.s

我注意到Apple还没有发布Xcode 5.x开发工具的来源

请访问http://www.opensource.apple.com/,最新版本为4.6

我打算对其中一个工具(ld64)进行一些改进,我想使用最新版本的源代码.

在ld64(APSL)的特定情况下,他们没有义务释放源,但是对于git这样的GPL工具(假设他们做了一些改变,很可能).所以,我觉得奇怪的是他们还没有释放它们.

有人可以更熟悉www.opensource.apple.com告诉我他们在发布新版XCode后通常需要多长时间才能更新网站？

谢谢!